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
1 |
7 = 7 = 5 + 2 = 3 + 2 + 2 |
Definir la función
1 |
particiones :: Int -> [[Int]] |
tal que (particiones n) es el comjunto de las particiones primas de n. Por ejemplo,
1 2 3 4 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
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) |