Menu Close

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>

2 soluciones de “Partición por suma

  1. Rubén Muñoz Mkrtchian
    import Data.List ((), inits)
     
    particion :: Int -> [Int] -> [[Int]]
    particion _ [] = []
    particion n xs
      | any (>n) xs = []
      | otherwise   = ps : particion n (xs  ps)
           where ps = last (takeWhile ((<=n) . sum) (inits xs))
  2. Adrián García Ruiz
    particion :: Int -> [Int] -> [[Int]]
    particion n xs | any (>n) xs = []
                   | otherwise = foldl f [[]] xs
      where f yss x | sum (last yss) + x > n = yss ++ [[x]] 
                    | otherwise = init yss ++ [(last yss) ++ [x]]

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.