Sucesión infinita de todas las palabras

José A. Alonso

31-05-2016

El conjunto de todas las palabras se puede ordenar como en los diccionarios:

  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

palabras :: [String]
posicion :: String -> Integer

tales que

palabras es la lista ordenada de todas las palabras. Por ejemplo,

λ> 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,

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

posicion (palabras `genericIndex` n) == n

Soluciones

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.