Una partici\u00f3n de un entero positivo n es una manera de escribir n como una suma de enteros positivos. Dos sumas que s\u00f3lo difieren en el orden de sus sumandos se consideran la misma partici\u00f3n. Por ejemplo, 4 tiene cinco particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n particiones :: Int -> [[Int]]\n<\/pre>\ntal que (particiones n)<\/code> es la lista de las particiones del n\u00famero n<\/code>. Por ejemplo,<\/p>\n\n particiones 4 == [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]\n particiones 5 == [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]\n length (particiones 50) == 204226\n<\/pre>\nSoluciones<\/h4>\n\nmodule Particiones_de_enteros_positivos where\n\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nparticiones1 :: Int -> [[Int]]\nparticiones1 0 = [[]]\nparticiones1 n = [x:y | x <- [n,n-1..1],\n y <- particiones1 (n-x),\n [x] >= take 1 y]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nparticiones2 :: Int -> [[Int]]\nparticiones2 n = aux !! n\n where\n aux = [] : map particiones [1..]\n particiones m = [m] : [x:p | x <- [m,m-1..1],\n p <- aux !! (m-x),\n x >= head p]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nparticiones3 :: Int -> [[Int]]\nparticiones3 n = aux n n\n where aux 0 _ = [[]]\n aux n' m = concat [map (i:) (aux (n'-i) i)\n | i <- [n',n'-1..1], i <= m]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nparticiones4 :: Int -> [[Int]]\nparticiones4 n = aux n n\n where aux 0 _ = [[]]\n aux n' m = concat [map (i:) (aux (n'-i) i)\n | i <- [k,k-1..1]]\n where k = min m n'\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_particiones :: Positive Int -> Bool\nprop_particiones (Positive n) =\n all (== particiones1 n)\n [ particiones2 n\n , particiones3 n\n , particiones4 n\n ]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheckWith (stdArgs {maxSize=20}) prop_particiones\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia --\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> length (particiones1 23)\n-- 1255\n-- (12.50 secs, 6,614,487,992 bytes)\n-- \u03bb> length (particiones2 23)\n-- 1255\n-- (0.04 secs, 3,071,104 bytes)\n-- \u03bb> length (particiones3 23)\n-- 1255\n-- (0.02 secs, 9,163,544 bytes)\n-- \u03bb> length (particiones4 23)\n-- 1255\n-- (0.01 secs, 7,149,512 bytes)\n--\n-- \u03bb> length (particiones2 50)\n-- 204226\n-- (2.50 secs, 758,729,104 bytes)\n-- \u03bb> length (particiones3 50)\n-- 204226\n-- (4.26 secs, 2,359,121,096 bytes)\n-- \u03bb> length (particiones4 50)\n-- 204226\n-- (2.67 secs, 1,598,588,040 bytes)\n<\/pre>\n