Menu Close

Número de particiones de un conjunto

José A. Alonso,

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

Definir la función

   nParticiones :: [a] -> Integer

tal que (nParticiones xs) es el número de particiones de xs. Por ejemplo,

   nParticiones [1,2]                     ==  2
   nParticiones [1,2,3]                   ==  5
   nParticiones "abcd"                    ==  15
   length (show (nParticiones [1..500]))  ==  844

Soluciones

import Data.List  ( genericLength
                  )
import Data.Array ( Array
                  , (!)
                  , array
                  )
 
-- 1ª definición
-- =============
 
nParticiones :: [a] -> Integer
nParticiones xs =
  genericLength (particiones xs)
 
-- (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 :: [a] -> [[[a]]]
particiones [] = [[]]
particiones xs =
  concat [particionesFijas xs k | k <- [0..length xs]]
 
-- (particionesFijas xs k) es el conjunto de las particiones de xs en k
-- subconjuntos. Por ejemplo,
--    particionesFijas [1,2,3] 0  ==  []
--    particionesFijas [1,2,3] 1  ==  [[[1,2,3]]]
--    particionesFijas [1,2,3] 2  ==  [[[1],[2,3]],[[1,2],[3]],[[2],[1,3]]]
--    particionesFijas [1,2,3] 3  ==  [[[1],[2],[3]]]
--    particionesFijas [1,2,3] 4  ==  []
particionesFijas :: [a] -> Int -> [[[a]]]
particionesFijas [] _ = []
particionesFijas xs 1 = [[xs]]
particionesFijas (x:xs) k =
   [[x]:ys | ys <- particionesFijas xs (k-1)] ++
   concat [inserta x ys | ys <- particionesFijas xs k]
 
-- (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] 
 
-- 2ª definición
-- =============
 
nParticiones2 :: [a] -> Integer
nParticiones2 xs = sum [nParticionesFijas n k | k <- [0..n]]
  where n = genericLength xs
 
-- nPparticionesFijas n k) es el número de las particiones de un
-- conjunto con n elementos en k subconjuntos. Por ejemplo,
--    nParticionesFijas 3 0  ==  0
--    nParticionesFijas 3 1  ==  1
--    nParticionesFijas 3 2  ==  3
--    nParticionesFijas 3 3  ==  1
--    nParticionesFijas 3 4  ==  0
nParticionesFijas :: Integer -> Integer -> Integer
nParticionesFijas 0 0 = 1
nParticionesFijas 0 _ = 0
nParticionesFijas n 1 = 1
nParticionesFijas n k = nParticionesFijas (n-1) (k-1) + k * nParticionesFijas (n-1) k
 
-- 3ª definición
-- =============
 
nParticiones3 :: [a] -> Integer
nParticiones3 xs = sum [a ! (n,k) | k <- [0..n]]
  where n = genericLength xs
        a = matrizNParticiones n
 
-- (matrizNParticiones n) es la matriz de dimensión ((0,0),(n,n)) que en
-- la posición (i,j) tiene el número de particiones de un conjunto de i
-- elementos en j subconjuntos. Por ejemplo,
--    λ> matrizNParticiones 3
--    array ((0,0),(3,3))
--          [((0,0),0),((0,1),0),((0,2),0),((0,3),0),
--           ((1,0),0),((1,1),1),((1,2),0),((1,3),0),
--           ((2,0),0),((2,1),1),((2,2),1),((2,3),0),
--           ((3,0),0),((3,1),1),((3,2),3),((3,3),1)]
--    λ> matrizNParticiones 4
--    array ((0,0),(4,4))
--          [((0,0),0),((0,1),0),((0,2),0),((0,3),0),((0,4),0),
--           ((1,0),0),((1,1),1),((1,2),0),((1,3),0),((1,4),0),
--           ((2,0),0),((2,1),1),((2,2),1),((2,3),0),((2,4),0),
--           ((3,0),0),((3,1),1),((3,2),3),((3,3),1),((3,4),0),
--           ((4,0),0),((4,1),1),((4,2),7),((4,3),6),((4,4),1)]
matrizNParticiones :: Integer -> Array (Integer,Integer) Integer
matrizNParticiones n = a 
  where
    a = array ((0,0),(n,n)) [((i,j), f i j) | i <- [0..n], j <- [0..n]]
    f 0 0 = 1
    f 0 _ = 0
    f _ 0 = 0
    f _ 1 = 1
    f i j = a ! (i-1,j-1) + j * a ! (i-1,j)
 
-- 4ª definición
-- =============
 
nParticiones4 :: [a] -> Integer
nParticiones4 xs = sum [a ! (n,k) | k <- [0..n]]
  where
    n = genericLength xs
    a = array ((0,0),(n,n)) [((i,j), f i j) | i <- [0..n], j <- [0..n]]
    f 0 0 = 1
    f 0 _ = 0
    f _ 0 = 0
    f _ 1 = 1
    f i j = a ! (i-1,j-1) + j * a ! (i-1,j)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> nParticiones [1..11]
--    678570
--    (3.77 secs, 705,537,480 bytes)
--    λ> nParticiones2 [1..11]
--    678570
--    (0.07 secs, 6,656,584 bytes)
--    λ> nParticiones3 [1..11]
--    678570
--    (0.01 secs, 262,176 bytes)
--    λ> nParticiones4 [1..11]
--    678570
--    (0.01 secs, 262,264 bytes)
--    
--    λ> nParticiones2 [1..16]
--    10480142147
--    (2.24 secs, 289,774,408 bytes)
--    λ> nParticiones3 [1..16]
--    10480142147
--    (0.01 secs, 437,688 bytes)
--    λ> nParticiones4 [1..16]
--    10480142147
--    (0.01 secs, 437,688 bytes)
--    
--    λ> length (show (nParticiones3 [1..500]))
--    844
--    (2.23 secs, 357,169,528 bytes)
--    λ> length (show (nParticiones4 [1..500]))
--    844
--    (2.20 secs, 357,172,680 bytes)

Pensamiento

Yo he visto garras fieras en las pulidas manos;
conozco grajos mélicos y líricos marranos …
El más truhán se lleva la mano al corazón,
y el bruto más espeso se carga de razón.

Antonio Machado

Medio
, , , , , , ,

6 soluciones de “Número de particiones de un conjunto”

  1. Responder
    frahidzam 
    import Data.Matrix
 
nParticiones :: [a] -> Integer
nParticiones xs = getElem n n (matrizP n) 
  where n = length xs
        matrizP n = matrix n n ((i,j) -> aux (i,j))
          where aux (1,1) = 1
                aux (n,1) = aux (n-1,n-1)
                aux (1,n) = 0
                aux (i,j) = aux (i,j-1) + aux (i-1,j-1)
  2. Responder
    berarcmat 
    nParticiones :: [a] -> Integer
nParticiones xs = (matrizBell n) ! (n,1)
  where n = length xs
 
matrizBell :: Int -> Array (Int,Int) Integer
matrizBell n = q where
  q = array ((0,1),(n,n+1)) [((i,j),f i j) | i <- [0..n], j <- [1..n+1]]
  f 0 1 = 1
  f i 1 = q ! (i-1,i)
  f i j = q ! (i,j-1) + q ! (i-1,j-1)
  3. Responder
    luipromor 
    import Data.List (genericLength)
 
nParticiones :: [a] -> Integer
nParticiones = genericLength . particiones
 
particiones :: [a] -> [[[a]]]
particiones [x] = [[[x]]]
particiones xs = concat [aux xs n | n <- [1..length xs]]
  where
    aux _ 0 = []
    aux [] _ = []
    aux xs 1 = [[xs]]
    aux (x:xs) n = [[x]:ys | ys <- aux xs (n-1)] ++
                   concat [inserta x ys | ys <- aux xs n]
 
inserta :: a -> [[a]] -> [[[a]]]
inserta _ []  = []
inserta a yss = [aux yss k 1 | k <- [1..length yss]]
  where aux [] _ _ = []
        aux (xs:xss) k n | k == n    = (a:xs) : aux xss k (n+1)
                         | otherwise = xs : aux xss k (n+1)
  4. Responder
    adogargon

    Una definición por recursión

    nParticiones :: [a] -> Integer
nParticiones xs = last (lista (n-1))
  where
    n = length xs
    lista (-1) = [1]
    lista 0    = [1]
    lista 1    = [1,2]
    lista n    = last (lista (n-1)) : zipWith (+) (lista n) (lista (n-1))
  6. Responder
    javmarcha1 
    import Data.List
 
nParticiones :: (Ord a) => [a] -> Integer
nParticiones xs = fromIntegral (length (particiones xs))
 
particiones :: Ord a => [a] -> [[[a]]]
particiones xs =
  [ dropWhile (== []) (sort yss)
  | yss <- producto (lista3 (lista2 (lista xs)))
  , sort (concat yss) == xs]
 
lista :: Ord a => [a] -> [[a]]
lista xs = sort (tail (subsequences xs))
 
lista2 :: Eq a => [[a]] -> [[[a]]]
lista2 []  = []
lista2 xss = takeWhile (elem (head (head xss))) xss :
             lista2 (dropWhile (elem (head (head xss))) xss)
 
lista3 :: [[[a]]] -> [[[a]]]
lista3 = map ([]:) 
 
producto :: [[[a]]] -> [[[a]]]
producto []         = [[]]
producto (xss:xsss) = [xs:yss | xs <- xss, yss <- producto xsss]

Escribe tu solución

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