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 |
Nota: Se recomienda usar programación dinámica.
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) |
Sin programación dinámica