Sucesión infinita de todas las palabras
El conjunto de todas las palabras se puede ordenar como en los diccionarios:
|
1 2 3 4 5 6 7 8 |
a, b, ..., z, A, B, ..., Z, aa, ab, ..., az, aA, aB, ..., aZ, ba, bb, ..., bz, bA, bB, ..., bZ, ... za, zb, ..., zz, zA, zB, ..., zZ, aaa, aab, ..., aaz, aaA, aaB, ..., aaZ, baa, bab, ..., baz, baA, baB, ..., baZ, ... |
Definir las funciones
|
1 2 |
palabras :: [String] posicion :: String -> Integer |
tales que
- palabras es la lista ordenada de todas las palabras. Por ejemplo,
|
1 2 3 4 5 6 |
λ> take 10 (drop 100 palabras) ["aW","aX","aY","aZ","ba","bb","bc","bd","be","bf"] λ> take 10 (drop 2750 palabras) ["ZU","ZV","ZW","ZX","ZY","ZZ","aaa","aab","aac","aad"] λ> palabras !! (10^6) "gePO" |
- (posicion n) es la palabra que ocupa la posición n en la lista ordenada de todas las palabras. Por ejemplo,
|
1 2 3 4 5 6 7 |
posicion "c" == 2 posicion "ab" == 53 posicion "ba" == 104 posicion "eva" == 14664 posicion "adan" == 151489 posicion "HoyEsMartes" == 4957940944437977046 posicion "EnUnLugarDeLaMancha" == 241779893912461058861484239910864 |
Comprobar con QuickCheck que para todo entero positivo n se verifica que
|
1 |
posicion (palabras `genericIndex` n) == n |
Soluciones
[schedule expon=’2016-06-07′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 07 de junio.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
[/schedule]
[schedule on=’2016-06-07′ at=»06:00″]
|
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 |
import Data.List (genericIndex, genericLength) import Test.QuickCheck -- 1ª definición de palabras -- ========================= palabras1 :: [String] palabras1 = concatMap palabrasDeLongitud [1..] -- (palabrasDeLongitud n) es la lista ordenada de palabras longitud -- n. Por ejemplo, -- take 3 (palabrasDeLongitud 2) == ["aa","ab","ac"] -- take 3 (palabrasDeLongitud 3) == ["aaa","aab","aac"] palabrasDeLongitud :: Integer -> [String] palabrasDeLongitud 1 = [[x] | x <- letras] palabrasDeLongitud n = [x:ys | x <- letras, ys <- palabrasDeLongitud (n-1)] -- letras es la lista ordenada de las letras. letras :: [Char] letras = ['a'..'z'] ++ ['A'..'Z'] -- 2ª definición de palabras -- ========================= palabras2 :: [String] palabras2 = concat (iterate f elementales) where f = concatMap (\x -> map (x++) elementales) -- elementales es la lista de las palabras de una letra. elementales :: [String] elementales = map (:[]) letras -- 3ª definición de palabras -- ========================= palabras3 :: [String] palabras3 = tail $ map reverse aux where aux = "" : [c:cs | cs <- aux, c <- letras] -- Comparación -- =========== -- λ> palabras1 !! (10^6) -- "gePO" -- (0.87 secs, 480,927,648 bytes) -- λ> palabras2 !! (10^6) -- "gePO" -- (0.11 secs, 146,879,840 bytes) -- λ> palabras3 !! (10^6) -- "gePO" -- (0.25 secs, 203,584,608 bytes) -- 1ª definición de posicion -- ========================= posicion1 :: String -> Integer posicion1 cs = genericLength (takeWhile (/=cs) palabras1) -- 1ª definición de posicion -- ========================= posicion2 :: String -> Integer posicion2 "" = -1 posicion2 (c:cs) = (1 + posicionLetra c) * 52^(length cs) + posicion2 cs posicionLetra :: Char -> Integer posicionLetra c = genericLength (takeWhile (/=c) letras) -- La propiedad es prop_palabras :: (Positive Integer) -> Bool prop_palabras (Positive n) = posicion2 (palabras3 `genericIndex` n) == n -- La comprobación es -- λ> quickCheck prop_palabras -- +++ OK, passed 100 tests. |
[/schedule]
Otra reescritura: