Máxima suma en una matriz
Las matrices puede representarse mediante tablas cuyos índices son pares de números naturales:
type Matriz = Array (Int,Int) Int
Definir la función
maximaSuma :: Matriz -> Int
tal que (maximaSuma p) es el máximo de las sumas de las listas de elementos de la matriz p tales que cada elemento pertenece sólo a una fila y a una columna. Por ejemplo,
λ> maximaSuma (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7]) 17
ya que las selecciones, y sus sumas, de la matriz
|1 2 3| |8 4 9| |5 6 7|
son
[1,4,7] --> 12 [1,9,6] --> 16 [2,8,7] --> 17 [2,9,5] --> 16 [3,8,6] --> 17 [3,4,5] --> 12
Hay dos selecciones con máxima suma: [2,8,7] y [3,8,6].
Soluciones
import Data.Array import Data.List (permutations) type Matriz = Array (Int,Int) Int maximaSuma :: Matriz -> Int maximaSuma p = maximum [sum xs | xs <- selecciones p] -- (selecciones p) es la lista de las selecciones en las que cada -- elemento pertenece a un única fila y a una única columna de la matriz -- p. Por ejemplo, -- λ> selecciones (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7]) -- [[1,4,7],[2,8,7],[3,4,5],[2,9,5],[3,8,6],[1,9,6]] selecciones :: Matriz -> [[Int]] selecciones p = [[p!(i,j) | (i,j) <- ijs] | ijs <- [zip [1..n] xs | xs <- permutations [1..n]]] where (_,(m,n)) = bounds p -- 2ª solución (mediante submatrices): maximaSuma2 :: Matriz -> Int maximaSuma2 p | (m,n) == (1,1) = p!(1,1) | otherwise = maximum [p!(1,j) + maximaSuma2 (submatriz 1 j p) | j <- [1..n]] where (_,(m,n)) = bounds p -- (submatriz i j p) es la matriz obtenida a partir de la p eliminando -- la fila i y la columna j. Por ejemplo, -- λ> submatriz 2 3 (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7]) -- array ((1,1),(2,2)) [((1,1),1),((1,2),2),((2,1),5),((2,2),6)] submatriz :: Int -> Int -> Matriz -> Matriz submatriz i j p = array ((1,1), (m-1,n -1)) [((k,l), p ! f k l) | k <- [1..m-1], l <- [1.. n-1]] where (_,(m,n)) = bounds p f k l | k < i && l < j = (k,l) | k >= i && l < j = (k+1,l) | k < i && l >= j = (k,l+1) | otherwise = (k+1,l+1)