Menu Close

Particiones de enteros positivos

 

Una partición de un entero positivo n es una manera de escribir n como una suma de enteros positivos. Dos sumas que sólo difieren en el orden de sus sumandos se consideran la misma partición. Por ejemplo, 4 tiene cinco particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.

Definir la función

   particiones :: Int -> [[Int]]

tal que (particiones n) es la lista de las particiones del número
n. Por ejemplo,

   particiones 4  ==  [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]
   particiones 5  ==  [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]
   length (particiones 50)  ==  204226

Soluciones

import Data.List (sort)
 
-- 1ª solución
particiones :: Int -> [[Int]]
particiones 0 = [[]]
particiones n = [x:y | x <- [n,n-1..1], 
                       y <- particiones (n-x), 
                       [x] >= take 1 y]
 
-- 2ª solución
particiones2 :: Int -> [[Int]]
particiones2 n = aux !! n where
  aux = [] : map particiones [1..]  
  particiones n = [n] : [x:p | x <- [n,n-1..1], 
                               p <- aux !! (n-x), 
                               x >= head p]
 
-- Comparación de eficiencia                                        --
-- =========================
 
-- La comparación es
--    λ> length (particiones 20)
--    627
--    (4.93 secs, 875288184 bytes)
-- 
--    λ> length (particiones2 20)
--    627
--    (0.02 secs, 2091056 bytes)

Pensamiento

Fe empirista. Ni somos ni seremos.
Todo nuestro vivir es emprestado.
Nada trajimos, nada llevaremos.

Antonio Machado

Avanzado

4 soluciones de “Particiones de enteros positivos

  1. frahidzam
    particiones :: Int -> [[Int]]
    particiones n = particionAux !! n
      where
        particionAux = [] : map part [1..]
        part n       = [n] : [x:p | x <- [n,n-1..1]
                                  , p <- particionAux !! (n-x)
                                  , x >= head p]
  2. berarcmat
    import Data.List (nub)
     
    particiones :: Int -> [[Int]]
    particiones n =
      reverse (sumando
               (map reverse
                (nub
                 (map sort
                  (particionesLista
                   (replicate n 1))))))
     
    particionesLista :: [Int] -> [[[Int]]]
    particionesLista [] = [[]]
    particionesLista xs =
      [take k xs : yss | k <- [1..n]
                       , yss <- particionesLista (drop k xs)]
      where n = length xs
     
    sumando :: [[[Int]]] ->[[Int]]
    sumando (xss:xsss) = map sum xss: sumando xsss
    sumando []         = []
  3. luipromor
    particiones :: Int -> [[Int]]
    particiones 1 = [[1]]
    particiones n = (nub . map sort . concat) (map f (particiones (n-1)))
      where f xs     = [xs ++ [1], g xs]
            g (x:xs) = (x+1) : xs
  4. javmarcha1
    import Data.List
     
    particiones :: Int -> [[Int]]
    particiones 1 = [[1]]
    particiones n =reverse(sort(nub[reverse(sort xs)
                | xs <- (particion3 [[x] |x <- [1..n]] n)]))
     
    particion3 :: [[Int]] -> Int -> [[Int]]
    particion3 [] n = []
    particion3 xss n =[[n]] ++ [zs | zs <- [ xs ++ [x] |
               x <- [1..(quot n 2)], xs <- xss], sum zs == n]
               ++ nub[sort ws |ws <- (particion3 (nub[sort ys | ys <- [ xs ++ [x] |
               x <- [1..(quot n 2)],xs <- xss], sum ys <= n]) n)]

Los comentarios están cerrados.