Menu Close

Máxima suma en una matriz

José A. Alonso,

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,

   ghci> 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,
--    ghci> 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, 
--    ghci> 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)
Avanzado
, , , , , , ,

6 soluciones de “Máxima suma en una matriz”

  1. Responder
    fracruzam

    Por fuerza bruta:

    import Data.Array
import Data.List
 
type Matriz = Array (Int,Int) Int
 
maximaSuma :: Matriz -> Int 
maximaSuma p = maximum (map (sum . map (p!)) (ix n))
  where n = fst $ snd $ bounds p
 
ix :: Int -> [[(Int,Int)]]
ix n = map ((x,y) -> zip x y) $
       zip (permutations [1..n]) (repeat [1..n])
  2. Responder
    abrdelrod 
    import Data.Array
 
type Matriz = Array (Int,Int) Int
 
-- Funciones auxiliares:
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) = snd $ 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)
 
elemsFilCol :: Matriz -> [[Int]]
elemsFilCol p | any (==1) [m,n] = [[x] | x <- elems p]
              | otherwise =  concat [map (x:) (elemsFilCol (submatriz i 1 p)) | ((i,1),x) <- assocs p]
                         where (m,n) = snd $ bounds p
-- La que se pide:
maximaSuma :: Matriz -> Int
maximaSuma = maximum . map sum . elemsFilCol
  3. Responder
    manvermor 
    import Data.Array
import Data.List
 
type Matriz = Array (Int,Int) Int
 
maximaSuma :: Matriz -> Int
maximaSuma p = maximum [ sum xs | xs <- elecciones p]
 
-- Funcion Auxiliar
elecciones :: (Enum t, Num t, Ix t) => Array (t, t) e -> [[e]]
elecciones p = 
 [ [ p!(i,j) | (i,j) <- indices ] | indices <- [ zip [1..m] xs | xs <- permutations [1..n]]]
    where (_,(m,n)) = bounds p
  4. Responder
    erisan 
    import Data.List
import Data.Array
type Matriz = Array (Int,Int) Int
 
maximaSuma :: Matriz -> Int
maximaSuma m = maximum [sum xs | xs <- separa z (posiciones m)]
             where z = snd (snd ( bounds m))
 
 
 
posiciones :: (Enum a, Num a, Ix a) => Array (a, a) t -> [t]
posiciones x = [x!(i,j) | (i,j) <- (permutaciones (snd (snd (bounds x))))]
 
permutaciones :: (Enum b, Num b) => b -> [(b, b)]
permutaciones n =  concat [zip [1..n] xss | xss <- permutations [1..n]]
 
separa :: Int -> [a] -> [[a]]
separa _ [] = []
separa n xs = take n xs : separa n (drop n xs)
  5. Responder
    ivaruicam 
    import Data.Matrix
import Data.Array
 
type Matriz = Array (Int,Int) Int
 
-- Todas las posibles listas
listasMatriz :: Matrix a -> [[a]]
listasMatriz p |nrows p == 1 = [toList p]
               |otherwise = [(getElem 1 j p) : ys | j <- [1..ncols p], ys <-
                                                 listasMatriz
                                                 (minorMatrix 1 j p)]
 
-- Convertir una matriz del tipo array en otra del tipo matrix
arrayToMatrix :: Array (Int, Int) a -> Matrix a
arrayToMatrix p = ((a,b) xs -> fromList a b xs) (snd(bounds p)) (elems p)
 
-- La función que pedían
maximaSuma :: Matriz -> Int
maximaSuma = maximum . map sum . listasMatriz . arrayToMatrix
  6. Responder
    Chema Cortés 
    import Data.Array
import Data.List (permutations)
 
type Matriz = Array (Int,Int) Int
 
maximaSuma :: Matriz -> Int
maximaSuma p = maximum [ sum (map (p!) xs) | xs <- xss ]
    where (_,(a,b)) = bounds p
          xss = [zip [1..a] xs | xs <- permutations [1..b]]

Escribe tu solución

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