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
No sé si es así la propiedad porque supongo que debe de dar para todas las listas, la vacía incluida
Propiedad corregida y comprobada