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}} {{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
particiones :: [a] -> [[[a]]] bell :: Integer -> Integer
tales que
- (particiones xs) es el conjunto de las particiones de xs. Por ejemplo,
λ> 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,
λ> 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
- B(0) = 1
- \(B(n) = \Sigma_{k=0}^{n-1} \binom{n-1}{k} B(k)\)
Soluciones
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.