Particiones de longitud fija
Enunciado
|
1 2 3 4 5 6 |
-- Definir la función -- particionesFijas :: Int -> Int -> [[Int]] -- tal que (particionesFijas n k) es la lista de listas de k números -- naturales no crecientes cuya suma es n. Por ejemplo, -- ghci> particionesFijas 8 3 -- [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]] |
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 |
-- 1ª definición particionesFijas :: Int -> Int -> [[Int]] particionesFijas n 1 = [[n]] particionesFijas n k | k < 1 = [] | otherwise = [x:y:ys | x <- [1..n-1], (y:ys) <- particionesFijas (n-x) (k-1), x >= y] -- 2ª definición particionesFijas2 :: Int -> Int -> [[Int]] particionesFijas2 n k | k <= 0 = [] | k == 1 = [[n]] | k == n = [replicate k 1] | k > n = [] | otherwise = [xs ++ [1] | xs <- particionesFijas2 (n-1) (k-1)] ++ [[x+1 | x <- xs] | xs <- particionesFijas2 (n-k) k] -- Comparación: -- ghci> length (particionesFijas 800 3) -- 53333 -- (1.01 secs, 97696476 bytes) -- -- ghci> length (particionesFijas2 800 3) -- 53333 -- (4.52 secs, 693969028 bytes) |