Máxima suma en una matriz

PorJosé A. Alonso 11-marzo-201628-marzo-2016

Las matrices puede representarse mediante tablas cuyos índices son pares de números naturales:

   type Matriz = Array (Int,Int) Int

1	type Matriz = Array (Int,Int) Int

Definir la función

   maximaSuma :: Matriz -> Int

1	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

1 2	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|

|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

[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)

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)

6 Comentarios

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])

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])

Responder

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

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

Responder

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

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

Responder

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)

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)

Responder

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

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

Responder

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]]

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]]

Responder

Máxima suma en una matriz

Soluciones

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico