Particiones de longitud fija
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,
λ> particionesFijas 8 2 [[4,4],[5,3],[6,2],[7,1]] λ> particionesFijas 8 3 [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]] λ> particionesFijas 9 3 [[3,3,3],[4,3,2],[4,4,1],[5,2,2],[5,3,1],[6,2,1],[7,1,1]] λ> length (particionesFijas 67 5) 8056
Soluciones
-- 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: -- λ> length (particionesFijas 800 3) -- 53333 -- (1.01 secs, 97696476 bytes) -- -- λ> length (particionesFijas2 800 3) -- 53333 -- (4.52 secs, 693969028 bytes)