Problema de las particiones óptimas
El problema de la particiones óptimas consiste en dada una lista xs dividirla en dos sublistas ys y zs tales que el valor absoluto de la diferencia de la suma de los elementos de xs y la suma de los elemento de zs sea lo menor posible.Cada una de estas divisiones (ys,zs) es una partición óptima de xs. Por ejemplo, la partición óptima de [2,3,5] es ([2,3],[5]) ya que |(2+3) – 5| = 0. Una lista puede tener distintas particiones óptimas. Por ejemplo, [1,1,2,3] tiene dos particiones óptimas ([1,2],[1,3]) y ([1,1,2],[3]) ambas con diferencia 1 (es decir, 1 = |(1+2)-(1+3)| = |(1+1+2)-3|).
Definir la función
|
1 |
particionesOptimas :: [Int] -> [([Int],[Int])] |
tal que (particionesOptimas xs) es la lista de las particiones óptimas de xs. Por ejemplo,
|
1 2 |
particionesOptimas [2,3,5] == [([2,3],[5])] particionesOptimas [1,1,2,3] == [([1,2],[1,3]),([1,1,2],[3])] |
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 28 29 30 31 32 33 34 35 36 37 38 39 |
import Data.List ((\\), nub, sort, subsequences) -- Una partición es un par de lista de enteros. type Particion = ([Int],[Int]) -- (particiones xs) es la lista de las particiones de xs. Por ejemplo, -- λ> particiones [2,3,5] -- [([],[2,3,5]),([2],[3,5]),([2,3],[5]),([2,5],[3])] particiones :: [Int] -> [Particion] particiones xs = [(sort ys, sort zs) | ys <- subsequences xs , let zs = xs \\ ys , ys <= zs] -- (diferencia p) es el valor absoluto de la diferencia de las sumas de -- los elementos de la partición p. Por ejemplo, -- diferencia ([2],[3,5]) == 6 -- diferencia ([2,3],[5]) == 0 diferencia :: Particion -> Int diferencia (xs,ys) = abs (sum xs - sum ys) -- (diferenciasParticiones xs) es la lista de las diferencias de las -- particiones de xs. Por ejemplo, -- diferenciasParticiones [2,3,5] == [10,6,0,4] diferenciasParticiones :: [Int] -> [Int] diferenciasParticiones xs = map diferencia (particiones xs) -- (minDiferenciaParticiones xs) es el mínimo de las diferencias de las -- particiones de xs. Por ejemplo, -- minDiferenciaParticiones [2,3,5] == 0 -- minDiferenciaParticiones [1,1,2,3] == 1 minDiferenciaParticiones :: [Int] -> Int minDiferenciaParticiones = minimum . diferenciasParticiones particionesOptimas :: [Int] -> [Particion] particionesOptimas xs = nub [(ys,zs) | (ys,zs) <- particiones xs , diferencia (ys,zs) == m] where m = minDiferenciaParticiones xs |
Para la lista [5,0,5] da [([5],[0,5]),([5,0],[5])], pero los dos elementos representan la misma partición.