Menu Close

Caminos en una matriz

José A. Alonso,

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 )

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

Definir la función

   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

Nota: Se recomienda usar programación dinámica.

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)
Posted in Medio
Tagged , , , , , , , , ,

3 Comments

  1. melgonaco
    Responder 
    caminos :: Matrix Int -> [[Int]]
caminos m = map reverse ((matrizCaminos m) ! (a,b))
  where (a,b) = (nrows m, ncols m)
 
matrizCaminos :: Matrix Int -> Matrix [[Int]]
matrizCaminos m = p where
  (a,b) = (nrows m, ncols m)
  p = matrix a b f
  f (1,1) = [[m ! (1,1)]]
  f (1,j) = map (m ! (1,j):) (p ! (1,j-1))
  f (i,1) = map (m ! (i,1):) (p ! (i-1,1))
  f (i,j) = map (m ! (i,j):) (p ! (i,j-1) ++ p ! (i-1,j))
  2. Enrique Zubiría
    Responder

    Sin programación dinámica

    import Data.Matrix
 
caminos :: Matrix Int -> [[Int]]
caminos m = caminosAux 1 1
  where nf = nrows m
        nc = ncols m
        caminosAux i j
          | i  < nf && j  < nc  = map (m!(i,j):) (concat [caminosAux (i+1) j, caminosAux i (j+1)])
          | i  < nf && j == nc  = map (m!(i,j):) (caminosAux (i+1) j)
          | i == nf && j  < nc  = map (m!(i,j):) (caminosAux i (j+1))
          | otherwise = [[m!(i,j)]]
  3. Enrique Zubiría
    Responder 
    import Data.Matrix
 
caminos m = mC!(rows, cols)
  where mC = matrix rows cols ((i, j) -> f i j)
        rows = nrows m
        cols = ncols m
        f i j
          | i == j && j == 1 = [[m!(1,1)]]
          | i == 1 = map (++[m!(i,j)]) (mC!(i, j-1))
          | j == 1 = map (++[m!(i,j)]) (mC!(i-1, j))
          | otherwise = map (++[m!(i,j)]) (concat [mC!(i, j-1), mC!(i-1, j)])

Escribe tu solución

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