Menu Close

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) = \displaystyle \sum_{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.

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.

Una solución de “Números de Bell

  1. fercarnav
    import Test.QuickCheck
    import Data.List
     
    bell :: Integer -> Integer
    bell 0 = 1
    bell x = genericLength (particiones [0..x-1])
     
    particiones :: [a] -> [[[a]]]
    particiones []  = []
    particiones [a] = [[[a]]]
    particiones (x:xs) =
      concat (map (pegadoA x) (particiones xs))
      ++ juntoA x (particiones xs)
     
    juntoA :: a -> [[[a]]] -> [[[a]]]
    juntoA x xss = map ([x]:) xss
     
    pegadoA :: a -> [[a]] -> [[[a]]]
    pegadoA x [] = []
    pegadoA x (ys:yss) = [(x:ys):yss] ++ (map (ys:) (pegadoA x yss))
     
    factorial :: Integer -> Integer
    factorial 0 = 1
    factorial x = foldr1 (*) [1..x]
     
    numeroBell :: Integer -> Integer
    numeroBell 0 = 1
    numeroBell x =
      sum [(div (factorial (x-1))
                ((factorial k) * factorial (x-1-k))) * numeroBell k
          | k <- [0..x-1]]
     
    prop_bell :: Integer -> Bool
    prop_bell x =
      bell (abs x) == numeroBell (abs x)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.