Intersecciones parciales
Definir la función
|
1 |
interseccionParcial :: Ord a => Int -> [[a]] -> [a] |
tal que (interseccionParcial n xss) es la lista de los elementos que pertenecen al menos a n conjuntos de xss. Por ejemplo,
|
1 2 3 4 |
interseccionParcial 1 [[3,4],[4,5,9],[5,4,7]] == [3,4,5,9,7] interseccionParcial 2 [[3,4],[4,5,9],[5,4,7]] == [4,5] interseccionParcial 3 [[3,4],[4,5,9],[5,4,7]] == [4] interseccionParcial 4 [[3,4],[4,5,9],[5,4,7]] == [] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
import Data.List (foldl', nub, union, sort) import Test.QuickCheck -- 1ª solución -- =========== interseccionParcial1 :: Ord a => Int -> [[a]] -> [a] interseccionParcial1 n xss = [x | x <- sort (elementos xss) , pertenecenAlMenos n xss x] elementos :: Ord a => [[a]] -> [a] elementos [] = [] elementos (xs:xss) = xs `union` elementos xss pertenecenAlMenos :: Ord a => Int -> [[a]] -> a -> Bool pertenecenAlMenos n xss x = length [xs | xs <- xss, x `elem` xs] >= n -- 2ª solución -- =========== interseccionParcial2 :: Ord a => Int -> [[a]] -> [a] interseccionParcial2 n xss = [x | x <- sort (elementos2 xss) , pertenecenAlMenos2 n xss x] elementos2 :: Ord a => [[a]] -> [a] elementos2 = foldl' union [] pertenecenAlMenos2 :: Ord a => Int -> [[a]] -> a -> Bool pertenecenAlMenos2 n xss x = length (filter (x `elem`) xss) >= n -- 3ª solución -- =========== interseccionParcial3 :: Ord a => Int -> [[a]] -> [a] interseccionParcial3 n xss = [x | x <- sort (nub (concat xss)) , length [xs | xs <- xss, x `elem` xs] >= n] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_interseccionParcial :: Positive Int -> [[Int]] -> Bool prop_interseccionParcial (Positive n) xss = all (== interseccionParcial1 n yss) [interseccionParcial2 n yss, interseccionParcial3 n yss] where yss = map nub xss -- La comprobación es -- λ> quickCheck prop_interseccionParcial -- +++ OK, passed 100 tests. |
El código se encuentra en GitHub.