Descomposiciones como sumas de n sumandos
Enunciado
1 2 3 4 5 6 7 8 9 10 |
-- Definir la función -- sumas :: (Num a, Ord a) => Int -> [a] -> a -> [[a]] -- tal que (sumas n ys x) es la lista de las descomposiciones de x como -- sumas de n sumandos en la lista ns. Por ejemplo, -- sumas 2 [1,2] 3 == [[1,2],[2,1]] -- sumas 2 [1,2] 4 == [[2,2]] -- sumas 2 [1,2] 5 == [] -- sumas 3 [1,2] 5 == [[1,2,2],[2,1,2],[2,2,1]] -- sumas 3 [1,2] 6 == [[2,2,2]] -- sumas 2 [1,2,5] 6 == [[1,5],[5,1]] |
Soluciones
1 2 3 4 5 |
sumas :: (Num a, Ord a) => Int -> [a] -> a -> [[a]] sumas 1 ys x | x `elem` ys = [[x]] | otherwise = [] sumas n ys x = concat [[y:zs | zs <- sumas (n-1) ys (x-y)] | y <- ys, y <= x] |
Referencia
El ejercicio está basado en el problema del 11 de junio de 1HaskellADay.