Particiones primas

Una partición prima de un número natural n es un conjunto de primos cuya suma es n. Por ejemplo, el número 7 tiene 7 particiones primas ya que

   7 = 7 = 5 + 2 = 3 + 2 + 2

1	7 = 7 = 5 + 2 = 3 + 2 + 2

Definir la función

   particiones :: Int -> [[Int]]

1	particiones :: Int -> [[Int]]

tal que (particiones n) es el comjunto de las particiones primas de n. Por ejemplo,

   particiones 7             ==  [[7],[5,2],[3,2,2]]
   particiones 8             ==  [[5,3],[3,3,2],[2,2,2,2]]
   particiones 9             ==  [[7,2],[5,2,2],[3,3,3],[3,2,2,2]]
   length (particiones 100)  ==  40899

particiones 7 == [[7],[5,2],[3,2,2]]

particiones 8 == [[5,3],[3,3,2],[2,2,2,2]]

particiones 9 == [[7,2],[5,2,2],[3,3,3],[3,2,2,2]]

length (particiones 100) == 40899

Soluciones

import Data.Numbers.Primes (primes)
import Data.Array          (Array, (!), array)

-- 1ª solución
-- ===========

particiones1 :: Int -> [[Int]]
particiones1 0 = [[]]
particiones1 n = [x:y | x <- xs, 
                        y <- particiones1 (n-x), 
                        [x] >= take 1 y]
  where xs = reverse (takeWhile (<= n) primes)

-- 2ª solución (con programación dinámica)
-- =======================================

particiones2 :: Int -> [[Int]]
particiones2 n = (vectorParticiones n) ! n

-- (vectorParticiones n) es el vector con índices de 0 a n tal que el
-- valor del índice k es la lista de las particiones primas de k. Por
-- ejemplo, 
--    λ> mapM_ print (elems (vectorParticiones 9))
--    [[]]
--    []
--    [[2]]
--    [[3]]
--    [[2,2]]
--    [[5],[3,2]]
--    [[3,3],[2,2,2]]
--    [[7],[5,2],[3,2,2]]
--    [[5,3],[3,3,2],[2,2,2,2]]
--    [[7,2],[5,2,2],[3,3,3],[3,2,2,2]]
--    λ> elems (vectorParticiones 9) == map particiones1 [0..9]
--    True
vectorParticiones :: Int -> Array Int [[Int]]
vectorParticiones n = v where
  v = array (0,n) [(i,f i) | i <- [0..n]]
    where f 0 = [[]]
          f m = [x:y | x <- xs, 
                       y <- v ! (m-x), 
                       [x] >= take 1 y]
            where xs = reverse (takeWhile (<= m) primes)

-- Comparación de eficiencia
-- =========================

--    λ> length (particiones1 35)
--    175
--    (5.88 secs, 2,264,266,040 bytes)
--    λ> length (particiones2 35)
--    175
--    (0.02 secs, 1,521,560 bytes)

import Data.Numbers.Primes (primes)

import Data.Array (Array, (!), array)

-- 1ª solución

-- ===========

particiones1 :: Int -> [[Int]]

particiones1 0 = [[]]

particiones1 n = [x:y | x <- xs,

y <- particiones1 (n-x),

[x] >= take 1 y]

where xs = reverse (takeWhile (<= n) primes)

-- 2ª solución (con programación dinámica)

-- =======================================

particiones2 :: Int -> [[Int]]

particiones2 n = (vectorParticiones n) ! n

-- (vectorParticiones n) es el vector con índices de 0 a n tal que el

-- valor del índice k es la lista de las particiones primas de k. Por

-- ejemplo,

-- λ> mapM_ print (elems (vectorParticiones 9))

-- [[]]

-- []

-- [[2]]

-- [[3]]

-- [[2,2]]

-- [[5],[3,2]]

-- [[3,3],[2,2,2]]

-- [[7],[5,2],[3,2,2]]

-- [[5,3],[3,3,2],[2,2,2,2]]

-- [[7,2],[5,2,2],[3,3,3],[3,2,2,2]]

-- λ> elems (vectorParticiones 9) == map particiones1 [0..9]

-- True

vectorParticiones :: Int -> Array Int [[Int]]

vectorParticiones n = v where

v = array (0,n) [(i,f i) | i <- [0..n]]

where f 0 = [[]]

f m = [x:y | x <- xs,

y <- v ! (m-x),

[x] >= take 1 y]

where xs = reverse (takeWhile (<= m) primes)

-- Comparación de eficiencia

-- =========================

-- λ> length (particiones1 35)

-- 175

-- (5.88 secs, 2,264,266,040 bytes)

-- λ> length (particiones2 35)

-- 175

-- (0.02 secs, 1,521,560 bytes)

4 Comentarios

import Data.Numbers.Primes

particiones :: Int -> [[Int]]
particiones n = aux n primosHastaN
 where primosHastaN = takeWhile (<= n) primes
       aux 0 _ = [[]]
       aux _ [] = []
       aux m (x:xs) | x > m = []
                    | otherwise = [x:zs | zs <- aux (m-x) (x:xs)] ++ aux m xs

import Data.Numbers.Primes

particiones :: Int -> [[Int]]

particiones n = aux n primosHastaN

where primosHastaN = takeWhile (<= n) primes

aux 0 _ = [[]]

aux _ [] = []

aux m (x:xs) | x > m = []

| otherwise = [x:zs | zs <- aux (m-x) (x:xs)] ++ aux m xs

Responder

import Data.Numbers.Primes (primes)
import Data.Matrix

particiones :: Int -> [[Int]]
particiones n = m!(n,n)
  where m = matrix n n f
        f (i,j) = concat [map (p:) (g (j-p) (min (j-p) p))
                          | p <- takeWhile (<= i) primes]
        g x y | x == 0 = [[]]
              | otherwise = m!(y,x)

import Data.Numbers.Primes (primes)

import Data.Matrix

particiones :: Int -> [[Int]]

particiones n = m!(n,n)

where m = matrix n n f

f (i,j) = concat [map (p:) (g (j-p) (min (j-p) p))

| p <- takeWhile (<= i) primes]

g x y | x == 0 = [[]]

| otherwise = m!(y,x)

Responder

import Data.Numbers.Primes
import Data.Array

particiones :: Int -> [[Int]]
particiones n = part ! n
  where part = array (1,n) [(i,lista i) | i<-[1..n]]
        lista 1 = []
        lista k | isPrime k = [k] : concat [(map (p:) (filter (\(x:xs) -> x <= p) (part ! (k-p)))) | p <- takeWhile (<k) primes]
                | otherwise = concat [(map (p:) (filter (\(x:xs) -> x <= p) (part ! (k-p)))) | p <- takeWhile (<k) primes]

import Data.Numbers.Primes

import Data.Array

particiones :: Int -> [[Int]]

particiones n = part ! n

where part = array (1,n) [(i,lista i) | i<-[1..n]]

lista 1 = []

lista k | isPrime k = [k] : concat [(map (p:) (filter (\(x:xs) -> x <= p) (part ! (k-p)))) | p <- takeWhile (<k) primes]

| otherwise = concat [(map (p:) (filter (\(x:xs) -> x <= p) (part ! (k-p)))) | p <- takeWhile (<k) primes]

Responder

import Data.Numbers.Primes
import Data.List

raizCuadrada :: Int -> Int
raizCuadrada = floor . sqrt . fromIntegral

divisible :: Int -> Int -> Bool
divisible a b = (a `mod` b) == 0

primos :: [Int]
primos = 2 : [x | x <- [3,5..], all (not . divisible x) (takeWhile (<= raizCuadrada x) primes)]

creciente :: [Int] -> Bool
creciente xs = and $ zipWith (<=) xs (tail xs)

listaP = map particion [0..]
    where particion x = filter creciente . mconcat $ map (\pr -> if pr == x then [[pr]] else map (pr:) (listaP !! (x - pr))) (takeWhile (<= x) primos)

particiones :: Int -> [[Int]]
particiones n = listaP !! n

-- Eficiencia

-- λ> particiones 12
-- [[2,2,2,2,2,2],[2,2,2,3,3],[2,2,3,5],[2,3,7],[2,5,5],[3,3,3,3],[5,7]]
-- (0.01 secs, 133,744 bytes)

-- λ> length (particiones 65)
-- 3079
-- (0.11 secs, 58,461,640 bytes)

import Data.Numbers.Primes

import Data.List

raizCuadrada :: Int -> Int

raizCuadrada = floor . sqrt . fromIntegral

divisible :: Int -> Int -> Bool

divisible a b = (a `mod` b) == 0

primos :: [Int]

primos = 2 : [x | x <- [3,5..], all (not . divisible x) (takeWhile (<= raizCuadrada x) primes)]

creciente :: [Int] -> Bool

creciente xs = and $ zipWith (<=) xs (tail xs)

listaP = map particion [0..]

where particion x = filter creciente . mconcat $ map (\pr -> if pr == x then [[pr]] else map (pr:) (listaP !! (x - pr))) (takeWhile (<= x) primos)

particiones :: Int -> [[Int]]

particiones n = listaP !! n

-- Eficiencia

-- λ> particiones 12

-- [[2,2,2,2,2,2],[2,2,2,3,3],[2,2,3,5],[2,3,7],[2,5,5],[3,3,3,3],[5,7]]

-- (0.01 secs, 133,744 bytes)

-- λ> length (particiones 65)

-- 3079

-- (0.11 secs, 58,461,640 bytes)

Responder

Particiones primas

Soluciones

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico