Menu Close

Caminos en una matriz (con programación dinámica)

José A. Alonso, ,

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 la derecha o abajo, son los siguientes:

   [1,6,11,2,8,9]
   [1,6,11,3,8,9]
   [1,6,12,3,8,9]
   [1,7,12,3,8,9]
   [1,6,11,3,4,9]
   [1,6,12,3,4,9]
   [1,7,12,3,4,9]
   [1,6,12,8,4,9]
   [1,7,12,8,4,9]
   [1,7, 3,8,4,9]

Definir la función

   caminos :: Matrix Int -> [[Int]]

tal que caminos m es la lista de los caminos en la matriz m desde extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia la derecha o abajo. Por ejemplo,

   λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   [[1,6,11,2,8,9],
    [1,6,11,3,8,9],
    [1,6,12,3,8,9],
    [1,7,12,3,8,9],
    [1,6,11,3,4,9],
    [1,6,12,3,4,9],
    [1,7,12,3,4,9],
    [1,6,12,8,4,9],
    [1,7,12,8,4,9],
    [1,7, 3,8,4,9]]
   λ> length (caminos (fromList 12 12 [1..]))
   705432

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

module Caminos_en_una_matriz where
 
import Data.Matrix (Matrix, (!), fromLists, matrix, nrows, ncols)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
-- 1ª definición (por recursión)
-- =============================
 
caminos1 :: Matrix Int -> [[Int]]
caminos1 m =
  reverse (map reverse (caminos1Aux m (nf,nc)))
  where nf = nrows m
        nc = ncols m
 
-- (caminos1Aux m p) es la lista de los caminos invertidos en la matriz m
-- desde la posición (1,1) hasta la posición p. 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)]
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> 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)
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    caminos1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` r
  it "e2" $
    caminos2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` r
  where r = [[1,6,11,2,8,9],
             [1,6,11,3,8,9],
             [1,6,12,3,8,9],
             [1,7,12,3,8,9],
             [1,6,11,3,4,9],
             [1,6,12,3,4,9],
             [1,7,12,3,4,9],
             [1,6,12,8,4,9],
             [1,7,12,8,4,9],
             [1,7, 3,8,4,9]]
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.0010 seconds
--    2 examples, 0 failures


Soluciones en Python

from collections import defaultdict
from sys import setrecursionlimit
from timeit import Timer, default_timer
 
setrecursionlimit(10**6)
 
# 1ª definición (por recursión)
# =============================
 
def caminos1(m: list[list[int]]) -> list[list[int]]:
    nf = len(m)
    nc = len(m[0])
    return list(reversed([list(reversed(xs)) for xs in caminos1Aux(m, (nf,nc))]))
 
# caminos1Aux(m, p) es la lista de los caminos invertidos en la matriz m
# desde la posición (1,1) hasta la posición p. Por ejemplo,
def caminos1Aux(m: list[list[int]], p: tuple[int, int]) -> list[list[int]]:
    (i, j) = p
    if p == (1,1):
        return [[m[0][0]]]
    if i == 1:
        return [[m[0][k-1] for k in range(j, 0, -1)]]
    if j == 1:
        return [[m[k-1][0] for k in range(i, 0, -1)]]
    return [[m[i-1][j-1]] + xs
            for xs in caminos1Aux(m, (i,j-1)) + caminos1Aux(m, (i-1,j))]
 
# 2ª solución (mediante programación dinámica)
# ============================================
 
def caminos2(p: list[list[int]]) -> list[list[int]]:
    m = len(p)
    n = len(p[0])
    return [list(reversed(xs)) for xs in diccionarioCaminos(p)[(m, n)]]
 
# diccionarioCaminos(p) es el diccionario cuyas claves son los
# puntos de la matriz p y sus valores son los caminos a dichos
# puntos. Por ejemplo,
#    >>> diccionarioCaminos([[1,6,11,2],[7,12,3,8],[3,8,4,9]])
#    defaultdict(<class 'list'>,
#                {(1, 1): [[1]],
#                 (1, 2): [[6, 1]],
#                 (1, 3): [[11, 6, 1]],
#                 (1, 4): [[2, 11, 6, 1]],
#                 (2, 1): [[7, 1]],
#                 (2, 2): [[12, 6, 1], [12, 7, 1]],
#                 (2, 3): [[3, 11, 6, 1], [3, 12, 6, 1], [3, 12, 7, 1]],
#                 (2, 4): [[8, 2, 11, 6, 1], [8, 3, 11, 6, 1],
#                          [8, 3, 12, 6, 1], [8, 3, 12, 7, 1]],
#                 (3, 1): [[3, 7, 1]],
#                 (3, 2): [[8, 12, 6, 1], [8, 12, 7, 1], [8, 3, 7, 1]],
#                 (3, 3): [[4, 3, 11, 6, 1], [4, 3, 12, 6, 1],
#                          [4, 3, 12, 7, 1], [4, 8, 12, 6, 1],
#                          [4, 8, 12, 7, 1], [4, 8, 3, 7, 1]],
#                 (3, 4): [[9, 8, 2, 11, 6, 1], [9, 8, 3, 11, 6, 1],
#                          [9, 8, 3, 12, 6, 1], [9, 8, 3, 12, 7, 1],
#                          [9, 4, 3, 11, 6, 1], [9, 4, 3, 12, 6, 1],
#                          [9, 4, 3, 12, 7, 1], [9, 4, 8, 12, 6, 1],
#                          [9, 4, 8, 12, 7, 1], [9, 4, 8, 3, 7, 1]]})
def diccionarioCaminos(p: list[list[int]]) -> dict[tuple[int, int], list[list[int]]]:
    m = len(p)
    n = len(p[0])
    q = defaultdict(list)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if i == 1:
                q[(i, j)] = [[p[0][z-1] for z in range(j, 0, -1)]]
            elif j == 1:
                q[(i, j)] = [[p[z-1][0] for z in range(i, 0, -1)]]
            else:
                q[(i, j)] = [[p[i-1][j-1]] + cs for cs in q[(i-1, j)] + q[(i, j-1)]]
    return q
 
# Comparación de eficiencia
# =========================
 
def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")
 
# La comparación es
#    >>> tiempo('caminos1([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')
#    2.20 segundos
#    >>> tiempo('caminos2([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')
#    0.64 segundos
 
# Verificación
# ============
 
def test_caminos() -> None:
    r = [[1, 6, 11, 2, 8, 9],
         [1, 6, 11, 3, 8, 9],
         [1, 6, 12, 3, 8, 9],
         [1, 7, 12, 3, 8, 9],
         [1, 6, 11, 3, 4, 9],
         [1, 6, 12, 3, 4, 9],
         [1, 7, 12, 3, 4, 9],
         [1, 6, 12, 8, 4, 9],
         [1, 7, 12, 8, 4, 9],
         [1, 7,  3, 8, 4, 9]]
    assert caminos1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == r
    assert caminos2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == r
    print("Verificado")
 
# La verificación es
#    >>> test_caminos()
#    Verificado
Leer más →

Caminos en una retícula (con programación dinámica)

José A. Alonso, ,

Se considera una retícula con sus posiciones numeradas, desde el vértice superior izquierdo, hacia la derecha y hacia abajo. Por ejemplo, la retícula de dimensión 3×4 se numera como sigue:

   |-------+-------+-------+-------|
   | (1,1) | (1,2) | (1,3) | (1,4) |
   | (2,1) | (2,2) | (2,3) | (2,4) |
   | (3,1) | (3,2) | (3,3) | (3,4) |
   |-------+-------+-------+-------|

Definir la función

   caminos :: (Int,Int) -> [[(Int,Int)]]

tal que caminos (m,n) es la lista de los caminos en la retícula de dimensión mxn desde (1,1) hasta (m,n). Por ejemplo,

   λ> caminos (2,3)
   [[(1,1),(1,2),(1,3),(2,3)],
    [(1,1),(1,2),(2,2),(2,3)],
    [(1,1),(2,1),(2,2),(2,3)]]
   λ> mapM_ print (caminos (3,4))
   [(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)]
   [(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)]
   [(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)]
   [(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)]
   [(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)]
   [(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)]
   [(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)]
   [(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)]
   [(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)]
   [(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

module Programacion_dinamica_Caminos_en_una_reticula where
 
import Data.Array (Array, (!), array)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
-- 1ª solución (por recursión)
-- ===========================
 
caminos1 :: (Int,Int) -> [[(Int,Int)]]
caminos1 p = map reverse (caminos1Aux p)
  where
    caminos1Aux (1,y) = [[(1,z) | z <- [y,y-1..1]]]
    caminos1Aux (x,1) = [[(z,1) | z <- [x,x-1..1]]]
    caminos1Aux (x,y) = [(x,y) : cs | cs <- caminos1Aux (x-1,y) ++
                                            caminos1Aux (x,y-1)]
 
-- 2ª solución (con programación dinámica)
-- =======================================
 
caminos2 :: (Int,Int) -> [[(Int,Int)]]
caminos2 p = map reverse (matrizCaminos p ! p)
 
matrizCaminos :: (Int,Int) -> Array (Int,Int) [[(Int,Int)]]
matrizCaminos (m,n) = q
  where
    q = array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]
    f 1 y = [[(1,z) | z <- [y,y-1..1]]]
    f x 1 = [[(z,1) | z <- [x,x-1..1]]]
    f x y = [(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> maximum (head (caminos1 (2000,2000)))
--    (2000,2000)
--    (0.01 secs, 3,459,576 bytes)
--    λ> maximum (head (caminos2 (2000,2000)))
--    (2000,2000)
--    (2.79 secs, 1,507,636,688 bytes)
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    caminos1 (2,3) `shouldBe`
    [[(1,1),(1,2),(1,3),(2,3)],
     [(1,1),(1,2),(2,2),(2,3)],
     [(1,1),(2,1),(2,2),(2,3)]]
  it "e2" $
    caminos2 (2,3) `shouldBe`
    [[(1,1),(1,2),(1,3),(2,3)],
     [(1,1),(1,2),(2,2),(2,3)],
     [(1,1),(2,1),(2,2),(2,3)]]
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.0010 seconds
--    2 examples, 0 failures


Soluciones en Python

from collections import defaultdict
from sys import setrecursionlimit
from timeit import Timer, default_timer
 
setrecursionlimit(10**6)
 
# 1ª solución (por recursión)
# ===========================
 
def caminos1(p: tuple[int, int]) -> list[list[tuple[int, int]]]:
    def aux(p: tuple[int, int]) -> list[list[tuple[int, int]]]:
        (x, y) = p
        if x == 1:
            return [[(1,z) for z in range(y, 0, -1)]]
        if y == 1:
            return [[(z,1) for z in range(x, 0, -1)]]
        return [[(x,y)] + cs for cs in aux((x-1,y)) + aux((x,y-1))]
 
    return [list(reversed(ps)) for ps in aux(p)]
 
# 2ª solución (con programación dinámica)
# =======================================
 
def caminos2(p: tuple[int, int]) -> list[list[tuple[int, int]]]:
    return [list(reversed(ps)) for ps in diccionarioCaminos(p)[p]]
 
 
# diccionarioCaminos((m,n)) es el diccionario cuyas claves son los
# puntos de la retícula mxn y sus valores son los caminos a dichos
# puntos. Por ejemplo,
#    >>> diccionarioCaminos((2,3))
#    defaultdict(<class 'list'>,
#                {(1,1): [[(1,1)]],
#                 (1,2): [[(1,2),(1,1)]],
#                 (1,3): [[(1,3),(1,2),(1,1)]],
#                 (2,1): [[(2,1),(1,1)]],
#                 (2,2): [[(2,2),(1,2),(1,1)],
#                         [(2,2),(2,1),(1,1)]],
#                 (2,3): [[(2,3),(1,3),(1,2),(1,1)],
#                         [(2,3),(2,2),(1,2),(1,1)],
#                         [(2,3),(2,2),(2,1),(1,1)]]})
def diccionarioCaminos(p: tuple[int, int]) -> dict[tuple[int, int], list[list[tuple[int, int]]]]:
    m, n = p
    q = defaultdict(list)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if i == 1:
                q[(i, j)] = [[(1, z) for z in range(j, 0, -1)]]
            elif j == 1:
                q[(i, j)] = [[(z, 1) for z in range(i, 0, -1)]]
            else:
                q[(i, j)] = [[(i, j)] + cs for cs in q[(i-1, j)] + q[(i, j-1)]]
    return q
 
# Comparación de eficiencia
# =========================
 
def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")
 
# La comparación es
#    >>> tiempo('max(caminos1((13,13))[0])')
#    26.75 segundos
#    >>> tiempo('max(caminos2((13,13))[0])')
#    7.40 segundos
 
# Verificación
# ============
 
def test_caminos() -> None:
    assert caminos1((2,3)) == \
        [[(1,1),(1,2),(1,3),(2,3)],
         [(1,1),(1,2),(2,2),(2,3)],
         [(1,1),(2,1),(2,2),(2,3)]]
    assert caminos2((2,3)) == \
        [[(1,1),(1,2),(1,3),(2,3)],
         [(1,1),(1,2),(2,2),(2,3)],
         [(1,1),(2,1),(2,2),(2,3)]]
    print("Verificado")
 
# La verificación es
#    >>> test_caminos()
#    Verificado
Leer más →

La distancia Levenshtein (con programación dinámica)

José A. Alonso, ,

La distancia de Levenshtein (o distancia de edición) es el mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Las operaciones de edición que se pueden hacer son:

  • insertar un carácter (por ejemplo, de «abc» a «abca»)
  • eliminar un carácter (por ejemplo, de «abc» a «ac»)
  • sustituir un carácter (por ejemplo, de «abc» a «adc»)

Por ejemplo, la distancia de Levenshtein entre «casa» y «calle» es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro:

   "casa"  --> "cala"  (sustitución de 's' por 'l')
   "cala"  --> "calla" (inserción de 'l' entre 'l' y 'a')
   "calla" --> "calle" (sustitución de 'a' por 'e')

Definir la función

   levenshtein :: String -> String -> Int

tal que levenshtein xs ys es la distancia de Levenshtein entre xs e ys. Por ejemplo,

   levenshtein "casa"  "calle"    ==  3
   levenshtein "calle" "casa"     ==  3
   levenshtein "casa"  "casa"     ==  0
   levenshtein "ana" "maria"      ==  3
   levenshtein "agua" "manantial" ==  7

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

module Levenshtein where
 
import Data.Array(Array, (!), array)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
-- 1ª definición (por recursión)
-- =============================
 
levenshtein1 :: String -> String -> Int
levenshtein1 "" ys = length ys
levenshtein1 xs "" = length xs
levenshtein1 c1@(x:xs) c2@(y:ys)
  | x == y    = levenshtein1 xs ys
  | otherwise = 1 + minimum [ levenshtein1 xs c2
                            , levenshtein1 c1 ys
                            , levenshtein1 xs ys]
 
-- 2ª definición (con programación dinámica)
-- =========================================
 
levenshtein2 :: String -> String -> Int
levenshtein2 xs ys = matrizLevenshtein xs ys ! (m,n)
  where  m = length xs
         n = length ys
 
-- (matrizLevenshtein xs ys) es la matriz cuyo número de filas es la
-- longitud de xs, cuyo número de columnas es la longitud de ys y en
-- valor en la posición (i,j) es la distancia de Levenshtein entre los
-- primeros i caracteres de xs y los j primeros caracteres de ys. Por
-- ejemplo,
--    λ> elems (matrizLevenshtein "casa" "calle")
--    [0,1,2,3,4,5,1,0,1,2,3,4,2,1,0,1,2,3,3,2,1,1,2,3,4,3,2,2,2,3]
-- Gráficamente,
--       c a l l e
--     0,1,2,3,4,5,
--  c  1,0,1,2,3,4,
--  a  2,1,0,1,2,3,
--  s  3,2,1,1,2,3,
--  a  4,3,2,2,2,3
matrizLevenshtein :: String -> String -> Array (Int,Int) Int
matrizLevenshtein xs ys = q where
  q = array ((0,0),(m,n)) [((i,j), f i j) | i <- [0..m], j <- [0..n]]
  m = length xs
  n = length ys
  f 0 j = j
  f i 0 = i
  f i j | xs !! (i-1) == ys !! (j-1) = q ! (i-1,j-1)
        | otherwise                  = 1 + minimum [ q ! (i-1,j)
                                                   , q ! (i,j-1)
                                                   , q ! (i-1,j-1)]
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> levenshtein1 (show (2^33)) (show (3^33))
--    12
--    (16.19 secs, 11,766,254,536 bytes)
--    λ> levenshtein2 (show (2^33)) (show (3^33))
--    12
--    (0.02 secs, 0 bytes)
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "ej1" $
    levenshtein1 "casa"  "calle"    `shouldBe`  3
  it "ej2" $
    levenshtein1 "calle" "casa"     `shouldBe`  3
  it "ej3" $
    levenshtein1 "casa"  "casa"     `shouldBe`  0
  it "ej4" $
    levenshtein1 "ana" "maria"      `shouldBe`  3
  it "ej5" $
    levenshtein1 "agua" "manantial" `shouldBe`  7
  it "ej6" $
    levenshtein2 "casa"  "calle"    `shouldBe`  3
  it "ej7" $
    levenshtein2 "calle" "casa"     `shouldBe`  3
  it "ej8" $
    levenshtein2 "casa"  "casa"     `shouldBe`  0
  it "ej9" $
    levenshtein2 "ana" "maria"      `shouldBe`  3
  it "ej10" $
    levenshtein2 "agua" "manantial" `shouldBe`  7
 
-- La verificación es
--    λ> verifica
--
--    ej1
--    ej2
--    ej3
--    ej4
--    ej5
--    ej6
--    ej7
--    ej8
--    ej9
--    ej10
--
--    Finished in 0.0024 seconds
--    10 examples, 0 failures


Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer
 
setrecursionlimit(10**6)
 
# 1ª definición (por recursión)
# =============================
 
def levenshtein1(xs: str, ys: str) -> int:
    if not xs:
        return len(ys)
    if not ys:
        return len(xs)
    if xs[0] == ys[0]:
        return levenshtein1(xs[1:], ys[1:])
    return 1 + min([levenshtein1(xs[1:], ys),
                    levenshtein1(xs, ys[1:]),
                    levenshtein1(xs[1:], ys[1:])])
 
 
# 2ª definición (con programación dinámica)
# =========================================
 
# matrizLevenshtein(xs, ys) es la matriz cuyo número de filas es la
# longitud de xs, cuyo número de columnas es la longitud de ys y en
# valor en la posición (i,j) es la distancia de Levenshtein entre los
# primeros i caracteres de xs y los j primeros caracteres de ys. Por
# ejemplo,
#    >>> matrizLevenshtein("casa", "calle")
#    [[0, 1, 2, 3, 4, 5],
#     [1, 0, 1, 2, 3, 4],
#     [2, 1, 0, 1, 2, 3],
#     [3, 2, 1, 1, 2, 3],
#     [4, 3, 2, 2, 2, 3]]
# Gráficamente,
#       c a l l e
#     0,1,2,3,4,5,
#  c  1,0,1,2,3,4,
#  a  2,1,0,1,2,3,
#  s  3,2,1,1,2,3,
#  a  4,3,2,2,2,3
def matrizLevenshtein(xs: str, ys: str) -> list[list[int]]:
    n = len(xs)
    m = len(ys)
    q = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        q[i][0] = i
    for j in range(m + 1):
        q[0][j] = j
    for i in range(1,n + 1):
        for j in range(1, m + 1):
            if xs[i - 1] == ys[j - 1]:
                q[i][j] = q[i - 1][j - 1]
            else:
                q[i][j] = 1 + min([q[i-1][j],  q[i][j-1], q[i-1][j-1]])
    return q
 
def levenshtein2(xs: str, ys: str) -> int:
    m = len(xs)
    n = len(ys)
    return matrizLevenshtein(xs, ys)[m][n]
 
# Comparación de eficiencia
# =========================
 
def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")
 
# La comparación es
#    >>> tiempo('levenshtein1(str(2**33), str(3**33))')
#    13.78 segundos
#    >>> tiempo('levenshtein2(str(2**33), str(3**33))')
#    0.00 segundos
 
# Verificación
# ============
 
def test_levenshtein() -> None:
    assert levenshtein1("casa",  "calle")     ==  3
    assert levenshtein1("calle", "casa")      ==  3
    assert levenshtein1("casa",  "casa")      ==  0
    assert levenshtein1("ana",   "maria")     ==  3
    assert levenshtein1("agua",  "manantial") ==  7
    assert levenshtein2("casa",  "calle")     ==  3
    assert levenshtein2("calle", "casa")      ==  3
    assert levenshtein2("casa",  "casa")      ==  0
    assert levenshtein2("ana",   "maria")     ==  3
    assert levenshtein2("agua",  "manantial") ==  7
    print("Verificado")
Leer más →

Subsecuencia común máxima (con programación dinámica)

José A. Alonso, ,

Si a una secuencia X de elementos (pongamos por ejemplo, le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, «aaoa» es una subsecuencia de la secuencia «amapola».

El término también se aplica cuando quitamos todos los elementos (es decir, la secuencia vacía es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de sí misma).

Dadas dos secuencias X e Y, decimos que Z es una subsecuencia de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = «amapola» e Y = «matamoscas», la secuencia «aaoa» es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 «maoa» o «amoa».

Definir la función

   scm :: Eq a => [a] -> [a] -> [a]

tal que scm xs ys es una de las subsecuencias comunes de longitud máxima de xs e ys. Por ejemplo,

   scm "amapola" "matamoscas" == "amoa"
   scm "atamos" "matamoscas"  == "atamos"
   scm "aaa" "bbbb"           == ""

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

module Subsecuencia_comun_maxima where
 
import Data.Array (Array, (!), array, listArray)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
-- 1ª definición (por recursión)
-- =============================
 
scm1 :: Eq a => [a] -> [a] -> [a]
scm1 [] _ = []
scm1 _ [] = []
scm1 (x:xs) (y:ys)
  | x == y    = x : scm1 xs ys
  | otherwise = mayor (scm1 (x:xs) ys) (scm1 xs (y:ys))
 
-- (mayor xs ys) es la cadena más larga de xs e ys.
--    mayor "hola" "buenas"  ==  "buenas"
--    mayor "hola" "pera"    ==  "hola"
mayor :: [a] -> [a] -> [a]
mayor xs ys
  | length xs >= length ys = xs
  | otherwise              = ys
 
-- 2ª definición (con programación dinámica)
-- =========================================
 
scm2 :: Eq a => [a] -> [a] -> [a]
scm2 xs ys = reverse (matrizSCM2 xs ys ! (n,m))
  where n = length xs
        m = length ys
 
-- (matrizSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n
-- y m son los números de elementos de xs e ys, respectivamente) tal que
-- el valor en la posición (i,j) es una SCM de los i primeros
-- elementos de xs y los j primeros elementos de ys. Por ejemplo,
--    λ> elems (matrizSCM2 "amapola" "matamoscas")
--    ["","","","","","","","","","","","","","a","a","a","a","a","a",
--     "a","a","a","","m","a","a","a","ma","ma","ma","ma","ma","ma","",
--     "m","am","am","aa","ma","ma","ma","ma","ama","ama","","m","am",
--     "am","aa","ma","ma","ma","ma","ama","ama","","m","am","am","aa",
--     "ma","oma","oma","oma","ama","ama","","m","am","am","aa","ma",
--     "oma","oma","oma","ama","ama","","m","am","am","aam","aam","oma",
--     "oma","oma","aoma","aoma"]
-- Gráficamente,
--        m   a    t    a     m     o     s     c     a      s
--    ["","" ,""  ,""  ,""   ,""   ,""   ,""   ,""   ,""    ,"",
-- a   "","" ,"a" ,"a" ,"a"  ,"a"  ,"a"  ,"a"  ,"a"  ,"a"   ,"a",
-- m   "","m","a" ,"a" ,"a"  ,"ma" ,"ma" ,"ma" ,"ma" ,"ma"  ,"ma",
-- a   "","m","am","am","aa" ,"ma" ,"ma" ,"ma" ,"ma" ,"ama" ,"ama",
-- p   "","m","am","am","aa" ,"ma" ,"ma" ,"ma" ,"ma" ,"ama" ,"ama",
-- o   "","m","am","am","aa" ,"ma" ,"oma","oma","oma","ama" ,"ama",
-- l   "","m","am","am","aa" ,"ma" ,"oma","oma","oma","ama" ,"ama",
-- a   "","m","am","am","aam","aam","oma","oma","oma","aoma","aoma"]
matrizSCM2 :: Eq a => [a] -> [a] -> Array (Int,Int) [a]
matrizSCM2 xs ys = q where
  q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]
  n = length xs
  m = length ys
  v = listArray (1,n) xs
  w = listArray (1,m) ys
  f 0 _ = []
  f _ 0 = []
  f i j | v ! i == w ! j = (v!i) : (q ! (i-1,j-1))
        | otherwise      = mayor (q ! (i-1,j)) (q ! (i,j-1))
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (scm1 (take 18 (cycle [1,3])) (take 18 (cycle [2,3])))
--    9
--    (20.17 secs, 11,436,759,992 bytes)
--    λ> length (scm2 (take 18 (cycle [1,3])) (take 18 (cycle [2,3])))
--    9
--    (0.00 secs, 1,013,624 bytes)
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    scm1 "amapola" "matamoscas" `shouldBe` "amoa"
  it "e2" $
    scm1 "atamos" "matamoscas"  `shouldBe` "atamos"
  it "e3" $
    scm1 "aaa" "bbbb"           `shouldBe` ""
  it "e4" $
    scm2 "amapola" "matamoscas" `shouldBe` "amoa"
  it "e5" $
    scm2 "atamos" "matamoscas"  `shouldBe` "atamos"
  it "e6" $
    scm2 "aaa" "bbbb"           `shouldBe` ""
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--    e5
--    e6
--
--    Finished in 0.0026 seconds
--    6 examples, 0 failures


Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer
 
setrecursionlimit(10**6)
 
# 1ª definición (por recursión)
# =============================
 
# (mayor xs ys) es la cadena más larga de xs e ys.
#    mayor "hola" "buenas"  ==  "buenas"
#    mayor "hola" "pera"    ==  "hola"
def mayor(xs: str, ys: str) -> str:
    if len(xs) >= len(ys):
        return xs
    return ys
 
def scm1(xs: str, ys: str) -> str:
    if not xs:
        return ""
    if not ys:
        return ""
    if xs[0] == ys[0]:
        return xs[0] + scm1(xs[1:], ys[1:])
    return mayor(scm1(xs, ys[1:]), scm1(xs[1:], ys))
 
# 2ª definición (con programación dinámica)
# =========================================
 
def scm2(xs: str, ys: str) -> str:
    n = len(xs)
    m = len(ys)
    return (matrizSCM2(xs, ys)[n][m])[::-1]
 
# matrizSCM2(xs, ys) es la matriz de orden (n+1)x(m+1) (donde n
# y m son los números de elementos de xs e ys, respectivamente) tal que
# el valor en la posición (i,j) es una SCM de los i primeros
# elementos de xs y los j primeros elementos de ys. Por ejemplo,
#    >>> matrizSCM2("amapola", "matamoscas")
#    [['', '', '', '', '', '', '', '', '', '', ''],
#     ['', '', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'],
#     ['', 'm', 'a', 'a', 'a', 'ma', 'ma', 'ma', 'ma', 'ma', 'ma'],
#     ['', 'm', 'am', 'am', 'aa', 'ma', 'ma', 'ma', 'ma', 'ama', 'ama'],
#     ['', 'm', 'am', 'am', 'aa', 'ma', 'ma', 'ma', 'ma', 'ama', 'ama'],
#     ['', 'm', 'am', 'am', 'aa', 'ma', 'oma', 'oma', 'oma', 'ama', 'ama'],
#     ['', 'm', 'am', 'am', 'aa', 'ma', 'oma', 'oma', 'oma', 'ama', 'ama'],
#     ['', 'm', 'am', 'am', 'aam', 'aam', 'oma', 'oma', 'oma', 'aoma', 'aoma']]
# Gráficamente,
#        m   a    t    a     m     o     s     c     a      s
#    ["","" ,""  ,""  ,""   ,""   ,""   ,""   ,""   ,""    ,"",
# a   "","" ,"a" ,"a" ,"a"  ,"a"  ,"a"  ,"a"  ,"a"  ,"a"   ,"a",
# m   "","m","a" ,"a" ,"a"  ,"ma" ,"ma" ,"ma" ,"ma" ,"ma"  ,"ma",
# a   "","m","am","am","aa" ,"ma" ,"ma" ,"ma" ,"ma" ,"ama" ,"ama",
# p   "","m","am","am","aa" ,"ma" ,"ma" ,"ma" ,"ma" ,"ama" ,"ama",
# o   "","m","am","am","aa" ,"ma" ,"oma","oma","oma","ama" ,"ama",
# l   "","m","am","am","aa" ,"ma" ,"oma","oma","oma","ama" ,"ama",
# a   "","m","am","am","aam","aam","oma","oma","oma","aoma","aoma"]
def matrizSCM2(xs: str, ys: str) -> list[list[str]]:
    n = len(xs)
    m = len(ys)
    q = [["" for _ in range(m + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if xs[i - 1] == ys[j - 1]:
                q[i][j] = xs[i - 1] + q[i - 1][j - 1]
            else:
                q[i][j] = mayor(q[i - 1][j], q[i][j - 1])
    return q
 
# # Comparación de eficiencia
# # =========================
 
def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")
 
# La comparación es
#    >>> tiempo('scm1(["1","3"]*9, ["2","3"]*9)')
#    8.44 segundos
#    >>> tiempo('scm2(["1","3"]*9, ["2","3"]*9)')
#    0.00 segundos
 
# Verificación
# ============
 
def test_scm() -> None:
    assert scm1("amapola", "matamoscas") == "amoa"
    assert scm1("atamos", "matamoscas")  == "atamos"
    assert scm1("aaa", "bbbb")           == ""
    assert scm2("amapola", "matamoscas") == "amoa"
    assert scm2("atamos", "matamoscas")  == "atamos"
    assert scm2("aaa", "bbbb")           == ""
    print("Verificado")
 
# La verificación es
#    >>> test_scm()
#    Verificado
Leer más →

Longitud de la subsecuencia común máxima (con programación dinámica)

José A. Alonso, ,

Si a una secuencia X de elementos (pongamos por ejemplo, caracteres) le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, «aaoa» es una subsecuencia de la secuencia «amapola».

El término también se aplica cuando quitamos todos los elementos (es decir, la secuencia vacía es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de sí misma).

Dadas dos secuencias X e Y, decimos que Z es una subsecuencia común de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = «amapola» e Y = «matamoscas», la secuencia «aaoa» es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 «maoa» o «amoa».

Se desea encontrar la longitud de las subsecuencias comunes más largas de dos secuencias de caracteres dadas.

Definir la función

   longitudSCM :: Eq a => [a] -> [a] -> Int

tal que longitudSCM xs ys es la longitud de la subsecuencia máxima de xs e ys. Por ejemplo,

   longitudSCM "amapola" "matamoscas" == 4
   longitudSCM "atamos" "matamoscas"  == 6
   longitudSCM "aaa" "bbbb"           == 0

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

module Longitud_SCM where
 
import Data.Array (Array,(!), array, listArray)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
-- 1ª definición (por recursión)
-- =============================
 
longitudSCM1 :: Eq a => [a] -> [a] -> Int
longitudSCM1 [] _ = 0
longitudSCM1 _ [] = 0
longitudSCM1 (x:xs) (y:ys)
  | x == y    = 1 + longitudSCM1 xs ys
  | otherwise = max (longitudSCM1 (x:xs) ys) (longitudSCM1 xs (y:ys))
 
-- 2ª definición (con programación dinámica)
-- =========================================
 
longitudSCM2 :: Eq a => [a] -> [a] -> Int
longitudSCM2 xs ys = matrizLongitudSCM2 xs ys ! (n,m)
  where n = length xs
        m = length ys
 
-- (matrizLongitudSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n
-- y m son los números de elementos de xs e ys, respectivamente) tal que
-- el valor en la posición (i,j) es la longitud de la SCM de los i
-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,
--    λ> elems (matrizLongitudSCM2 "amapola" "matamoscas")
--    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2,
--     0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3,
--     0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4]
-- Gráficamente,
--       m a t a m o s c a s
--    [0,0,0,0,0,0,0,0,0,0,0,
-- a   0,0,1,1,1,1,1,1,1,1,1,
-- m   0,1,1,1,1,2,2,2,2,2,2,
-- a   0,1,2,2,2,2,2,2,2,3,3,
-- p   0,1,2,2,2,2,2,2,2,3,3,
-- o   0,1,2,2,2,2,3,3,3,3,3,
-- l   0,1,2,2,2,2,3,3,3,3,3,
-- a   0,1,2,2,3,3,3,3,3,4,4]
matrizLongitudSCM2 :: Eq a => [a] -> [a] -> Array (Int,Int) Int
matrizLongitudSCM2 xs ys = q
  where
    n = length xs
    m = length ys
    v = listArray (1,n) xs
    w = listArray (1,m) ys
    q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]
      where f 0 _ = 0
            f _ 0 = 0
            f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)
                  | otherwise      = max (q ! (i-1,j)) (q ! (i,j-1))
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> longitudSCM1 (take 18 (cycle [1,3])) (take 18 (cycle [2,3]))
--    9
--    (13.90 secs, 8,883,660,048 bytes)
--    λ> longitudSCM2 (take 18 (cycle [1,3])) (take 18 (cycle [2,3]))
--    9
--    (0.01 secs, 953,880 bytes)
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    longitudSCM1 "amapola" "matamoscas" `shouldBe` 4
  it "e2" $
    longitudSCM1 "atamos" "matamoscas"  `shouldBe` 6
  it "e3" $
    longitudSCM1 "aaa" "bbbb"           `shouldBe` 0
  it "e4" $
    longitudSCM2 "amapola" "matamoscas" `shouldBe` 4
  it "e5" $
    longitudSCM2 "atamos" "matamoscas"  `shouldBe` 6
  it "e6" $
    longitudSCM2 "aaa" "bbbb"           `shouldBe` 0
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--    e5
--    e6
--
--    Finished in 0.0025 seconds
--    6 examples, 0 failures


Soluciones en Python

from timeit import Timer, default_timer
 
# 1ª definición (por recursión)
# =============================
 
def longitudSCM1(xs: str, ys: str) -> int:
    if not xs:
        return 0
    if not ys:
        return 0
    if xs[0] == ys[0]:
        return 1 + longitudSCM1(xs[1:], ys[1:])
    return max(longitudSCM1(xs, ys[1:]), longitudSCM1(xs[1:], ys))
 
# 2ª definición (con programación dinámica)
# =========================================
 
def longitudSCM2(xs: str, ys: str) -> int:
    n = len(xs)
    m = len(ys)
    return matrizLongitudSCM2(xs, ys)[n][m]
 
# matrizLongitudSCM2(xs, ys) es la matriz de orden (n+1)x(m+1) (donde n
# y m son los números de elementos de xs e ys, respectivamente) tal que
# el valor en la posición (i,j) es la longitud de la SCM de los i
# primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,
#    >>> matrizLongitudSCM2("amapola", "matamoscas")
#    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
#     [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
#     [0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2],
#     [0, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3],
#     [0, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3],
#     [0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3],
#     [0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3],
#     [0, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4]]
#    # Gráficamente,
#       m a t a m o s c a s
#    [0,0,0,0,0,0,0,0,0,0,0,
# a   0,0,1,1,1,1,1,1,1,1,1,
# m   0,1,1,1,1,2,2,2,2,2,2,
# a   0,1,2,2,2,2,2,2,2,3,3,
# p   0,1,2,2,2,2,2,2,2,3,3,
# o   0,1,2,2,2,2,3,3,3,3,3,
# l   0,1,2,2,2,2,3,3,3,3,3,
# a   0,1,2,2,3,3,3,3,3,4,4]
def matrizLongitudSCM2(xs: str, ys: str) -> list[list[int]]:
    n = len(xs)
    m = len(ys)
    q = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if xs[i - 1] == ys[j - 1]:
                q[i][j] = 1 + q[i - 1][j - 1]
            else:
                q[i][j] = max(q[i - 1][j], q[i][j - 1])
    return q
 
# Comparación de eficiencia
# =========================
 
def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")
 
# La comparación es
#    >>> tiempo('longitudSCM1([1,3]*9, [2,3]*9)')
#    8.04 segundos
#    >>> tiempo('longitudSCM2([1,3]*9, [2,3]*9)')
#    0.00 segundos
 
# Verificación
# ============
 
def test_longitudSCM() -> None:
    assert longitudSCM1("amapola", "matamoscas") == 4
    assert longitudSCM1("atamos", "matamoscas")  == 6
    assert longitudSCM1("aaa", "bbbb")           == 0
    assert longitudSCM2("amapola", "matamoscas") == 4
    assert longitudSCM2("atamos", "matamoscas")  == 6
    assert longitudSCM2("aaa", "bbbb")           == 0
    print("Verificado")
 
# La verificación es
#    >>> test_longitudSCM()
#    Verificado
Leer más →