Menu Close

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 )

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

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

3 soluciones de “Caminos en una matriz

  1. angruicam1
    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
  2. carriomon1

    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)]
  3. jorcatote

    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

Escribe tu solución

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