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}} |
{{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 |
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"]] |
λ> 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] |
λ> 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
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. |
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.”
Donald Knuth.