Caminos en una matriz

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

   (  1  6 11  2 )
   (  7 12  3  8 )
   (  3  8  4  9 )

( 1 6 11 2 )

( 7 12 3 8 )

( 3 8 4 9 )

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

   1, 7,  3, 8, 4, 9
   1, 7, 12, 8, 4, 9
   1, 7, 12, 3, 4, 9
   1, 7, 12, 3, 8, 9
   1, 6, 12, 8, 4, 9
   1, 6, 12, 3, 4, 9
   1, 6, 12, 3, 8, 9
   1, 6, 11, 3, 4, 9
   1, 6, 11, 3, 8, 9
   1, 6, 11, 2, 8, 9

1, 7, 3, 8, 4, 9

1, 7, 12, 8, 4, 9

1, 7, 12, 3, 4, 9

1, 7, 12, 3, 8, 9

1, 6, 12, 8, 4, 9

1, 6, 12, 3, 4, 9

1, 6, 12, 3, 8, 9

1, 6, 11, 3, 4, 9

1, 6, 11, 3, 8, 9

1, 6, 11, 2, 8, 9

Definir la función

   caminos :: Matrix Int -> [[Int]]

1	caminos :: Matrix Int -> [[Int]]

tal que (caminos m) es la lista de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

   λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   [[1,7, 3,8,4,9],
    [1,7,12,8,4,9],
    [1,7,12,3,4,9],
    [1,7,12,3,8,9],
    [1,6,12,8,4,9],
    [1,6,12,3,4,9],
    [1,6,12,3,8,9],
    [1,6,11,3,4,9],
    [1,6,11,3,8,9],
    [1,6,11,2,8,9]]
   λ> length (caminos (fromList 12 13 [1..]))
   1352078

λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

[[1,7, 3,8,4,9],

[1,7,12,8,4,9],

[1,7,12,3,4,9],

[1,7,12,3,8,9],

[1,6,12,8,4,9],

[1,6,12,3,4,9],

[1,6,12,3,8,9],

[1,6,11,3,4,9],

[1,6,11,3,8,9],

[1,6,11,2,8,9]]

λ> length (caminos (fromList 12 13 [1..]))

1352078

Soluciones

import Data.Matrix

-- 1ª definición de caminos (por recursión)
-- ----------------------------------------

caminos1 :: Matrix Int -> [[Int]]
caminos1 a = aux (1,1)
  where
    aux (i,j)
      | i == m           = [[a!(i,k) | k <- [j..n]]]
      | j == n           = [[a!(k,j) | k <- [i..m]]]
      | otherwise        = [a!(i,j) : cs | cs <- aux (i+1,j) ++ aux (i,j+1)]
      where m = nrows a
            n = ncols a

-- 2ª solución (mediante programación dinámica)
-- --------------------------------------------

caminos2 :: Matrix Int -> [[Int]]
caminos2 a = q ! (1,1)
  where
    q = matrix m n f
    m = nrows a
    n = ncols a
    f (i,j) | i == m    = [[a!(i,k) | k <- [j..n]]]
            | j == n    = [[a!(k,j) | k <- [i..m]]]
            | otherwise = [a!(i,j) : cs | cs <- q!(i+1,j) ++ q!(i,j+1)]  

-- 3ª solución
-- ===========

caminos3 :: Matrix Int -> [[Int]]
caminos3 a
  | m == 1 || n == 1 = [toList a]
  | otherwise = map (a ! (1,1):) (caminos3 (submatrix 2 m 1 n a) ++
                                  caminos3 (submatrix 1 m 2 n a)) 
  where m = nrows a
        n = ncols a

-- Comparación de eficiencia
-- -------------------------

--    λ> length (caminos1 (fromList 11 11 [1..]))
--    184756
--    (4.15 secs, 738,764,712 bytes)
--    λ> length (caminos2 (fromList 11 11 [1..]))
--    184756
--    (0.74 secs, 115,904,952 bytes)
--    λ> length (caminos3 (fromList 11 11 [1..]))
--    184756
--    (2.22 secs, 614,472,136 bytes)

import Data.Matrix

-- 1ª definición de caminos (por recursión)

-- ----------------------------------------

caminos1 :: Matrix Int -> [[Int]]

caminos1 a = aux (1,1)

where

aux (i,j)

| i == m = [[a!(i,k) | k <- [j..n]]]

| j == n = [[a!(k,j) | k <- [i..m]]]

| otherwise = [a!(i,j) : cs | cs <- aux (i+1,j) ++ aux (i,j+1)]

where m = nrows a

n = ncols a

-- 2ª solución (mediante programación dinámica)

-- --------------------------------------------

caminos2 :: Matrix Int -> [[Int]]

caminos2 a = q ! (1,1)

where

q = matrix m n f

m = nrows a

n = ncols a

f (i,j) | i == m = [[a!(i,k) | k <- [j..n]]]

| j == n = [[a!(k,j) | k <- [i..m]]]

| otherwise = [a!(i,j) : cs | cs <- q!(i+1,j) ++ q!(i,j+1)]

-- 3ª solución

-- ===========

caminos3 :: Matrix Int -> [[Int]]

caminos3 a

| m == 1 || n == 1 = [toList a]

| otherwise = map (a ! (1,1):) (caminos3 (submatrix 2 m 1 n a) ++

caminos3 (submatrix 1 m 2 n a))

where m = nrows a

n = ncols a

-- Comparación de eficiencia

-- -------------------------

-- λ> length (caminos1 (fromList 11 11 [1..]))

-- 184756

-- (4.15 secs, 738,764,712 bytes)

-- λ> length (caminos2 (fromList 11 11 [1..]))

-- 184756

-- (0.74 secs, 115,904,952 bytes)

-- λ> length (caminos3 (fromList 11 11 [1..]))

-- 184756

-- (2.22 secs, 614,472,136 bytes)

3 Comentarios

import Data.Matrix (Matrix, (!), nrows, ncols, fromLists, fromList)

caminos :: Matrix Int -> [[Int]]
caminos m = aux 1 1
  where aux i j
          | i == l && j == n = [[m!(i,j)]]
          | i == l           = [[m!(i,k) | k <- [j..n]]]
          | j == n           = [[m!(k,j) | k <- [i..l]]]
          | otherwise        =
            map (m!(i,j):) (aux (i+1) j)
            ++ map (m!(i,j):) (aux i (j+1))
            where l = nrows m
                  n = ncols m

import Data.Matrix (Matrix, (!), nrows, ncols, fromLists, fromList)

caminos m = aux 1 1

where aux i j

| i == l && j == n = [[m!(i,j)]]

| i == l = [[m!(i,k) | k <- [j..n]]]

| j == n = [[m!(k,j) | k <- [i..l]]]

| otherwise =

map (m!(i,j):) (aux (i+1) j)

++ map (m!(i,j):) (aux i (j+1))

where l = nrows m

n = ncols m

Responder

Una definición utilizando la definición por programación dinámica de la relación 29, aunque el resultado no lo da en el mismo orden.

import Data.Matrix

caminos :: Matrix Int -> [[Int]]
caminos p = map (map (\(i,j) -> p ! (i,j))) xs
  where xs = caminosPuntos (nrows p, ncols p)
 
caminosPuntos :: (Int,Int) -> [[(Int,Int)]]
caminosPuntos p = map reverse (matrizCaminos p ! p )
  where matrizCaminos (m,n) = q
          where q = matrix m n f
                f (1,y) = [[(1,z) | z<-[y,y-1..1]]]
                f (x,1) = [[(z,1) | z<-[x,x-1..1]]]
                f (x,y) = [(x,y) : xs | xs <- q ! (x-1,y) ++ q! (x,y-1)]

caminos p = map (map (\(i,j) -> p ! (i,j))) xs

where xs = caminosPuntos (nrows p, ncols p)

caminosPuntos :: (Int,Int) -> [[(Int,Int)]]

caminosPuntos p = map reverse (matrizCaminos p ! p )

where matrizCaminos (m,n) = q

where q = matrix m n f

f (1,y) = [[(1,z) | z<-[y,y-1..1]]]

f (x,1) = [[(z,1) | z<-[x,x-1..1]]]

f (x,y) = [(x,y) : xs | xs <- q ! (x-1,y) ++ q! (x,y-1)]

Definición bastante corta por recursión con la idea de ir reduciendo la matriz hasta una matriz fila o columna:

import Data.Matrix (nrows, ncols, submatrix)

caminos :: Matrix Int -> [[Int]]
caminos a
  | f == 1 || c == 1 = [toList a]
  | otherwise = map (a ! (1,1):) (caminos (submatrix 2 f 1 c a) ++
                                  caminos (submatrix 1 f 2 c a)) 
  where f = nrows a
        c = ncols a

import Data.Matrix (nrows, ncols, submatrix)

caminos a

| f == 1 || c == 1 = [toList a]

| otherwise = map (a ! (1,1):) (caminos (submatrix 2 f 1 c a) ++

caminos (submatrix 1 f 2 c a))

where f = nrows a

c = ncols a

Caminos en una matriz

Soluciones

3 Comentarios

Leave a Reply to jorcatoteCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

3 Comentarios

Leave a Reply to jorcatoteCancel reply

Entradas recientes

Buscar

Correo electrónico