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 m = map reverse (caminos1Aux m (nf,nc)) where nf = nrows m nc = ncols m -- (caminos1Aux p x) es la lista de los caminos invertidos en la matriz p -- desde la posición (1,1) hasta la posición x. Por ejemplo, caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]] caminos1Aux m (1,1) = [[m!(1,1)]] caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]] caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]] caminos1Aux m (i,j) = [m!(i,j) : xs | xs <- caminos1Aux m (i,j-1) ++ caminos1Aux m (i-1,j)] -- 2ª solución (mediante programación dinámica) -- -------------------------------------------- caminos2 :: Matrix Int -> [[Int]] caminos2 m = map reverse (matrizCaminos m ! (nrows m, ncols m)) matrizCaminos :: Matrix Int -> Matrix [[Int]] matrizCaminos m = q where q = matrix (nrows m) (ncols m) f f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]] f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]] f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)] -- Nota: (caminos2 m) es la inversa de (caminos1 m). -- Comparación de eficiencia -- ------------------------- -- λ> length (caminos1 (fromList 11 11 [1..])) -- 184756 -- (3.64 secs, 667,727,568 bytes) -- λ> length (caminos2 (fromList 11 11 [1..])) -- 184756 -- (0.82 secs, 129,181,072 bytes)