Menu Close

Día: 2 febrero, 2021

Partición por suma

Definir la función

   particion :: Int -> [Int] -> [[Int]]

tal que (particion n xs) es la lista de los elementos de xs, en el mismo orden, agrupados en listas con sumas menores o iguales que n. Por ejemplo,

   particion 6 [1,1,1,3,2,2,2,1,2,2,3]   ==  [[1,1,1,3],[2,2,2],[1,2,2],[3]]
   particion 5 [1,1,1,3,2,2,2,1,2,2,3]   ==  [[1,1,1],[3,2],[2,2,1],[2,2],[3]]
   particion 4 [1,1,1,3,2,2,2,1,2,2,3]   ==  [[1,1,1],[3],[2,2],[2,1],[2,2],[3]]
   particion 3 [1,1,1,3,2,2,2,1,2,2,3]   ==  [[1,1,1],[3],[2],[2],[2,1],[2],[2],[3]]
   particion 2 [1,1,1,3,2,2,2,1,2,2,3]   ==  []

Soluciones

particion :: Int -> [Int] -> [[Int]]
particion n xs = reverse (map reverse (aux xs [[]]))
  where aux []     yss      = yss
        aux (x:xs) (ys:yss) | x > n           = []
                            | x + sum ys <= n = aux xs ((x:ys):yss)
                            | otherwise       = aux xs ([x]:ys:yss)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>