Menu Close

Caminos en una retícula

José A. Alonso,

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.
C

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)
Posted in Medio
Tagged , , , , , ,

7 Comments

  1. erisan
    Responder 
    import Data.List
 
data Direccion = D | A deriving (Show, Eq)
type Camino = [Direccion]
 
 
caminos  :: Int -> Int -> [Camino]
caminos x y = nub (permutations (replicate y A ++ replicate x D))
 
nCaminos :: Int -> Int -> Integer
nCaminos x y = 
  factoriales !! (x + y) `div` (factoriales !! x * factoriales !! y)
 
 
factoriales :: [Integer]
factoriales = map snd aux
    where aux = iterate f (1,1) where f (x,y) = (x+1,x*y)
  2. fracruzam
    Responder 
    import Data.List
 
data Direccion = D | A deriving (Show, Eq)
type Camino = [Direccion]
 
caminos  :: Int -> Int -> [Camino]
caminos m n = busca [(0,0,[])]
  where busca :: [(Int,Int,Camino)] -> [Camino]
        busca ((a,b,xs):xss)
         | a == m && b == n = reverse xs: busca xss
         | a == m           = busca ((a,b+1,A:xs):             xss)
         |           b == n = busca (             (a+1,b,D:xs):xss)
         | otherwise        = busca ((a,b+1,A:xs):(a+1,b,D:xs):xss)
        busca [] = []
 
nCaminos :: Int -> Int -> Integer
nCaminos m n = product [b+1..a+b] `div` product [1..a]
  where [a,b] = map fromIntegral $ sort [n,m]
  3. carmengar
    Responder 
    import Data.List
 
data Direccion = A | D deriving (Show, Eq)
type Camino = [Direccion]
 
caminos :: Int -> Int -> [Camino]
caminos m n = (nub . permutations) (replicate m D ++ replicate n A)
 
nCaminos :: Int -> Int -> Integer
nCaminos m n = div (f (m'+n')) (f m' * f n')
               where f  = factorial 
                     n' = toInteger n
                     m' = toInteger m
 
factorial :: Integer -> Integer
factorial n = product [1..n]
  4. carruirui3
    Responder 
    caminos :: Int -> Int -> [Camino]
caminos m 0 = [replicate m A]
caminos 0 n = [replicate n D]
caminos m n = map (A:) (caminos (m-1) n) ++
              map (D:) (caminos m (n-1))
 
-- nCaminos es idéntica a la de fracruzam
nCaminos :: Int -> Int -> Integer
nCaminos m n = product [b+1..a+b] `div` product [1..a]
  where [a,b] = map fromIntegral $ sort [n,m]
  5. abrdelrod
    Responder

    Mediante búsqueda en espacios de estados (muy parecida a la de fracruzam):

    import I1M.BusquedaEnEspaciosDeEstados
 
data Direccion = D | A deriving (Show, Eq)
type Camino = [Direccion]
 
caminos  :: Int -> Int -> [Camino]
caminos m n = map fst $ buscaEE sucesores esFinal ([],(0,0))
    where sucesores (xs,(x,y)) | x == m = [(D:xs,(x,y+1))]
                               | y == n = [(A:xs,(x+1,y))]
                               | otherwise = [(D:xs,(x,y+1)),(A:xs,(x+1,y))]
          esFinal x = snd x == (m,n)

Escribe tu solución

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