Posiciones de conjuntos finitos de naturales
En un ejercicio anterior se mostró que 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.
Además, se definió 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]] |
Definir la función
1 |
posicion :: [Integer] -> Integer |
tal que (posicion xs) es la posición del conjunto finito de números naturales xs, representado por una lista decreciente, en enumeracionCFN. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 |
posicion [2,0] == 5 posicion [2,1] == 6 posicion [2,1,0] == 7 posicion [0] == 1 posicion [1,0] == 3 posicion [2,1,0] == 7 posicion [3,2,1,0] == 15 posicion [4,3,2,1,0] == 31 posicion [5,4,3,2,1,0] == 63 length (show (posicion [3*10^7])) == 9030900 |
Comprobar con QuickCheck que para todo número natural n,
1 |
posicion [n,n-1..0] == 2^(n+1) - 1. |
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 92 93 94 95 96 97 |
import Data.List (genericLength, nub, sort) import Test.QuickCheck -- 1ª solución -- =========== posicion :: [Integer] -> Integer posicion xs = genericLength (takeWhile (< xs) enumeracionCFN) 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 -- =========== posicion2 :: [Integer] -> Integer posicion2 [] = 0 posicion2 (x:xs) = 2^x + posicion2 xs -- 3ª solución -- =========== posicion3 :: [Integer] -> Integer posicion3 = foldr (\x -> (+) (2^x)) 0 -- 4ª solución -- =========== posicion4 :: [Integer] -> Integer posicion4 xs = sum [2^x | x <- xs ] -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_equiv :: [Integer] -> Bool prop_equiv xs = all (== posicion xs') [f xs' | f <- [ posicion2 , posicion3 , posicion4]] where xs' = reverse (sort (nub (map abs xs))) -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=15}) prop_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> posicion [19,18,17,16,14,9,6] -- 1000000 -- (2.61 secs, 1,754,265,776 bytes) -- λ> posicion2 [19,18,17,16,14,9,6] -- 1000000 -- (0.01 secs, 111,808 bytes) -- λ> posicion3 [19,18,17,16,14,9,6] -- 1000000 -- λ> posicion4 [19,18,17,16,14,9,6] -- 1000000 -- (0.01 secs, 111,704 bytes) -- λ> length (show (posicion2 [3*10^7])) -- 9030900 -- (2.06 secs, 571,911,304 bytes) -- λ> length (show (posicion3 [3*10^7])) -- 9030900 -- (2.06 secs, 571,911,544 bytes) -- λ> length (show (posicion4 [3*10^7])) -- 9030900 -- (2.05 secs, 571,911,464 bytes) -- Propiedad -- ========= -- La propiedad es prop_posicion :: Integer -> Property prop_posicion n = n >= 0 ==> posicion3 [n,n-1..0] == 2^(n+1) - 1 -- La comprobación es -- λ> quickCheck prop_posicion -- +++ OK, passed 100 tests. |
Pensamiento
¡Volar sin alas donde todo es cielo!
Antonio Machado