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 2 3 |
( 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 2 3 4 5 6 7 8 9 10 |
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
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,
1 2 3 4 5 6 7 8 9 10 11 12 13 |
λ> 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
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) |
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.
Definición bastante corta por recursión con la idea de ir reduciendo la matriz hasta una matriz fila o columna: