Números de Bell
Una partición de un conjunto A es un conjunto de subconjuntos no vacíos de A, disjuntos dos a dos y cuya unión es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones:
|
1 2 3 4 5 |
{{1}, {2}, {3}} {{1,2}, {3}} {{1,3}, {2}} {{1}, {2,3}} {{1,2,3}} |
El n-ésimo número de Bell, B(n), es el número de particiones de un conjunto de n elementos. Por lo visto anteriormentem B(3) = 5.
Definir las funciones
|
1 2 |
particiones :: [a] -> [[[a]]] bell :: Integer -> Integer |
tales que
- (particiones xs) es el conjunto de las particiones de xs. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> particiones [1,2] [[[1,2]],[[1],[2]]] λ> particiones [1,2,3] [[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[2],[1,3]],[[1],[2],[3]]] λ> particiones "abcd" [["abcd"],["a","bcd"],["ab","cd"],["b","acd"],["abc","d"],["bc","ad"], ["ac","bd"],["c","abd"],["a","b","cd"],["a","bc","d"],["a","c","bd"], ["ab","c","d"],["b","ac","d"],["b","c","ad"],["a","b","c","d"]] |
- (bell n) es el n-ésimo número de Bell. Por ejemplo,
|
1 2 3 4 |
λ> bell 3 5 λ> map bell [0..10] [1,1,2,5,15,52,203,877,4140,21147,115975] |
Comprobar con QuickCheck que (bell n) es equivalente a la función B(n) definida por
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 |
import Data.List (genericLength) import Test.QuickCheck -- Definición de particiones -- ========================= particiones :: [a] -> [[[a]]] particiones [] = [[]] particiones (x:xs) = concat [([x] : yss) : inserta x yss | yss <- ysss] where ysss = particiones xs -- (inserta x yss) es la lista obtenida insertando x en cada uno de los -- elementos de yss. Por ejemplo, -- λ> inserta 1 [[2,3],[4],[5,6,7]] -- [[[1,2,3],[4],[5,6,7]],[[2,3],[1,4],[5,6,7]],[[2,3],[4],[1,5,6,7]]] inserta :: a -> [[a]] -> [[[a]]] inserta _ [] = [] inserta x (ys:yss) = ((x:ys):yss) : [ys : zs | zs <- inserta x yss] -- Definición de Bell -- ================== bell :: Integer -> Integer bell n = genericLength (particiones [1..n]) -- Propiedad -- ========= prop_Bell :: Integer -> Property prop_Bell n = n >= 0 ==> bell n == b n b :: Integer -> Integer b 0 = 1 b n = sum [comb (n-1) k * b k | k <- [0..n-1]] comb :: Integer -> Integer -> Integer comb n k = product [n-k+1..n] `div` product [1..k] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_Bell -- +++ OK, passed 100 tests. |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
Pensamiento
«Cambiemos nuestra actitud tradicional en la construcción de programas. En lugar de imaginar que nuestra tarea principal es indicarle a una computadora lo que debe hacer, concentrémonos más bien en explicarle a los seres humanos lo que queremos que haga una computadora.»
Un comentario