Enumeración de conjuntos finitos de naturales
Los conjuntos finitos de números naturales se pueden enumerar como sigue
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
0: [] 1: [0] 2: [1] 3: [1,0] 4: [2] 5: [2,0] 6: [2,1] 7: [2,1,0] 8: [3] 9: [3,0] 10: [3,1] 11: [3,1,0] 12: [3,2] 13: [3,2,0] 14: [3,2,1] 15: [3,2,1,0] 16: [4] 17: [4,0] 18: [4,1] 19: [4,1,0] |
en la que los elementos están ordenados de manera decreciente.
Definir la constante
|
1 |
enumeracionCFN :: [[Integer]] |
tal que sus elementos son los conjuntos de los números naturales con la ordenación descrita anteriormente. Por ejemplo,
|
1 2 3 4 5 6 7 |
λ> take 20 enumeracionCFN [[], [0], [1],[1,0], [2],[2,0],[2,1],[2,1,0], [3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0], [4],[4,0],[4,1],[4,1,0]] |
Comprobar con QuickCheck que
- si (xs,ys) es un par de elementos consecutivos de enumeracionCFN, entonces xs < ys;
- todo conjunto finito de números naturales, representado por una lista decreciente, está en enumeracionCFN.
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
import Data.List (genericLength, nub, sort) import Test.QuickCheck -- 1ª solución -- =========== enumeracionCFN :: [[Integer]] enumeracionCFN = concatMap enumeracionCFNHasta [0..] -- (enumeracionCFNHasta n) es la lista de conjuntos con la enumeración -- anterior cuyo primer elemento es n. Por ejemplo, -- λ> enumeracionCFNHasta 1 -- [[1],[1,0]] -- λ> enumeracionCFNHasta 2 -- [[2],[2,0],[2,1],[2,1,0]] -- λ> enumeracionCFNHasta 3 -- [[3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0]] enumeracionCFNHasta :: Integer -> [[Integer]] enumeracionCFNHasta 0 = [[],[0]] enumeracionCFNHasta n = [n:xs | k <- [0..n-1], xs <- enumeracionCFNHasta k] -- 2ª solución -- =========== enumeracionCFN2 :: [[Integer]] enumeracionCFN2 = [] : aux 0 [[]] where aux n xs = yss ++ aux (n+1) (xs ++ yss) where yss = map (n:) xs -- 3ª solución -- =========== enumeracionCFN3 :: [[Integer]] enumeracionCFN3 = map conjunto [0..] -- (conjunto n) es el conjunto en la posición n. Por ejemplo, -- conjunto 6 == [2,1] conjunto :: Integer -> [Integer] conjunto n = reverse [x | (x,y) <- zip [0..] (binario n), y == 1] -- (binario n) es la representación binarioa del número n (en orden -- inverso). Por ejemplo, -- binario 6 == [0,1,1] binario :: Integer -> [Integer] binario 0 = [0] binario 1 = [1] binario n = n `mod` 2 : binario (n `div` 2) -- Comparación de eficiencia -- ========================= -- λ> enumeracionCFN !! (4*10^5) -- [18,17,12,11,9,7] -- (1.18 secs, 576,924,344 bytes) -- λ> enumeracionCFN2 !! (4*10^5) -- [18,17,12,11,9,7] -- (0.10 secs, 72,399,784 bytes) -- λ> enumeracionCFN3 !! (4*10^5) -- [18,17,12,11,9,7] -- (0.07 secs, 64,123,952 bytes) -- -- λ> enumeracionCFN2 !! (6*10^6) -- [22,20,19,17,16,15,11,10,8,7] -- (1.25 secs, 1,082,690,216 bytes) -- λ> enumeracionCFN3 !! (6*10^6) -- [22,20,19,17,16,15,11,10,8,7] -- (0.38 secs, 960,134,256 bytes) -- Propiedades -- =========== -- La primera propiedad es prop_enumeracionCFN :: Int -> Property prop_enumeracionCFN n = n >= 0 ==> xs < ys where (xs:ys:_) = drop n enumeracionCFN -- La comprobación es -- λ> quickCheck prop_enumeracionCFN -- +++ OK, passed 100 tests. -- La segunda propiedad es prop_completa :: [Integer] -> Bool prop_completa xs = xs' `elem` enumeracionCFN where xs' = reverse (sort (nub (map abs xs))) -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=15}) prop_completa -- +++ OK, passed 100 tests. |
Pensamiento
Junto al agua fría,
en la senda clara,
sombra dará algún día,
ese arbolillo en que nadie repara.Antonio Machado
3 Comentarios