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. |