Posiciones de conjuntos finitos de naturales

José A. Alonso

27-12-2019

En un ejercicio anterior se mostró que los conjuntos finitos de números naturales se pueden enumerar como sigue

 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

enumeracionCFN :: [[Integer]]

tal que sus elementos son los conjuntos de los números naturales con la ordenación descrita anteriormente. Por ejemplo,

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

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,

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

Comprobar con QuickCheck que para todo número natural n,

posicion [n,n-1..0] == 2^(n+1) - 1.

Soluciones

import Data.List (genericLength)
import Test.QuickCheck

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]

-- La propiedad es
prop_posicion :: Integer -> Property
prop_posicion n =
  n >= 0 ==> posicion [n,n-1..0] == 2^(n+1) - 1

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=15}) prop_posicion
--    +++ OK, passed 100 tests.