Caminos en una retícula
El problema de los caminos en una retícula consiste en, dada una retícula rectangular con m filas y n columnas, determinar todos los caminos para ir desde el vértice inferior izquierdo hasta el vértice superior derecho donde los movimientos permitidos son mover hacia el siguiente vértice a la derecha o arriba.
Por ejemplo, en la siguiente retícula un posible camino es el indicado en rojo.
Para representar los caminos se definen los siguientes tipos de datos:
data Direccion = D | A deriving (Show, Eq) type Camino = [Direccion]
Por tanto, el camino de la figura anterior se representa por la lista [D,D,A,D,A].
Definir las funciones
caminos :: Int -> Int -> [Camino] nCaminos :: Int -> Int -> Integer
tales que
- (caminos m n) es la lista de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,
λ> caminos 2 2 [[A,A,D,D],[A,D,A,D],[A,D,D,A],[D,A,A,D],[D,A,D,A],[D,D,A,A]] λ> caminos 1 3 [[A,A,A,D],[A,A,D,A],[A,D,A,A],[D,A,A,A]] λ> caminos 2 3 [[A,A,A,D,D],[A,A,D,A,D],[A,A,D,D,A],[A,D,A,A,D],[A,D,A,D,A],[A,D,D,A,A], [D,A,A,A,D],[D,A,A,D,A],[D,A,D,A,A],[D,D,A,A,A]]
- (nCaminos m n) es el número de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,
nCaminos 2 2 == 6 nCaminos 1 3 == 4 nCaminos 2 3 == 10 length (show (nCaminos 20000 30000)) == 14612 length (show (nCaminos 30000 20000)) == 14612
Soluciones
import Data.List (genericLength) data Direccion = D | A deriving (Show, Eq) type Camino = [Direccion] -- Definición de caminos -- ===================== caminos :: Int -> Int -> [Camino] caminos 0 n = [replicate n A] caminos m 0 = [replicate m D] caminos m n = [A:xs | xs <- caminos m (n-1)] ++ [D:xs | xs <- caminos (m-1) n] -- 1ª definición de nCaminos -- ========================= nCaminos1 :: Int -> Int -> Integer nCaminos1 m n = genericLength (caminos m n) -- 2ª definición de nCaminos -- ========================= nCaminos2 :: Int -> Int -> Integer nCaminos2 0 n = 1 nCaminos2 m 0 = 1 nCaminos2 m n = nCaminos2 m (n-1) + nCaminos2 (m-1) n -- 3ª definición de nCaminos -- ========================= -- Los caminos desde (0,0) a (m,n) son las permutaciones con repetición -- de m veces la D y n veces la A. Por tanto, su número es -- (m+n)! / m!*n! nCaminos3 :: Int -> Int -> Integer nCaminos3 m n = fact (m+n) `div` (fact m * fact n) fact :: Int -> Integer fact n = product [1..fromIntegral n] -- 4ª solución de nCaminos -- ======================= nCaminos4 :: Int -> Int -> Integer nCaminos4 m n = product [a+1..a+b] `div` product [2..b] where m' = fromIntegral m n' = fromIntegral n a = max m' n' b = min m' n' -- Comparación de eficiencia -- ========================= -- λ> nCaminos1 10 10 -- 184756 -- (3.50 secs, 656,909,648 bytes) -- λ> nCaminos2 10 10 -- 184756 -- (0.50 secs, 47,330,272 bytes) -- λ> nCaminos3 10 10 -- 184756 -- (0.01 secs, 0 bytes) -- λ> nCaminos4 10 10 -- 184756 -- (0.01 secs, 0 bytes) -- -- λ> nCaminos2 10 15 -- 3268760 -- (8.83 secs, 1,142,623,080 bytes) -- λ> nCaminos3 10 15 -- 3268760 -- (0.01 secs, 0 bytes) -- λ> nCaminos4 10 15 -- 3268760 -- (0.00 secs, 0 bytes) -- -- λ> let n = 2*10^4 -- (0.01 secs, 0 bytes) -- λ> length (show (nCaminos3 n n)) -- 12039 -- (8.41 secs, 2,369,767,480 bytes) -- λ> length (show (nCaminos4 n n)) -- 12039 -- (2.98 secs, 833,386,648 bytes)