El mes de septiembre en Exercitium (Ejercicios con Haskell y Python)
Durante el mes de septiembre he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Problema de suma cero (mediante espacio de estados)
- 2. Problema de las jarras (mediante espacios de estados)
- 3. La función de Fibonacci por programación dinámica
- 4. Coeficientes binomiales (con programación dinámica)
- 5. Longitud de la subsecuencia común máxima (con programación dinámica)
- 6. Subsecuencia común máxima (con programación dinámica)
A continuación se muestran las soluciones.
1. Problema de suma cero (mediante espacio de estados)
El problema de suma cero consiste en, dado el conjunto de enteros, encontrar sus subconjuntos no vacío cuyos elementos sumen cero.
Usando el procedimiento de búsqueda en profundidad, definir la función
1 |
suma0 :: [Int] -> [[Int]] |
tal que suma0 ns
es la lista de las soluciones del problema de suma cero para ns
. Por ejemplo,
1 2 3 4 5 6 |
λ> suma0 [-7,-3,-2,5,8] [[-3,-2,5]] λ> suma0 [-7,-3,-2,5,8,-1] [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]] λ> suma0 [-7,-3,1,5,8] [] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 52 53 54 55 56 |
module Problema_de_suma_cero where import BusquedaEnProfundidad (buscaProfundidad) import Data.List (delete, nub, sort) import Test.Hspec (Spec, hspec, it, shouldBe) -- Los estados son ternas formadas por los números seleccionados, su -- suma y los restantes números. type Estado = ([Int], Int, [Int]) inicial :: [Int] -> Estado inicial ns = ([],0,ns) esFinal :: Estado -> Bool esFinal (xs,s,_) = not (null xs) && s == 0 sucesores :: Estado -> [Estado] sucesores (xs,s,ns) = [(n:xs, n+s, delete n ns) | n <- ns] soluciones :: [Int] -> [Estado] soluciones ns = buscaProfundidad sucesores esFinal (inicial ns) suma0 :: [Int] -> [[Int]] suma0 ns = nub [sort xs | (xs,_,_) <- soluciones ns] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ suma0 [-7,-3,-2,5,8] `shouldBe` [[-3,-2,5]] it "e2" $ suma0 [-7,-3,-2,5,8,-1] `shouldBe` [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]] it "e3" $ suma0 [-7,-3,1,5,8] `shouldBe` [] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.0098 seconds -- 3 examples, 0 failures |
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 |
from src.BusquedaEnProfundidad import buscaProfundidad # Los estados son ternas formadas por los números seleccionados, su # suma y los restantes números. Estado = tuple[list[int], int, list[int]] def inicial(ns: list[int]) -> Estado: return ([], 0, ns) def esFinal(e: Estado) -> bool: (xs,s,_) = e return xs != [] and s == 0 def sucesores(e: Estado) -> list[Estado]: (xs, s, ns) = e return [([n] + xs, n + s, [m for m in ns if m !=n]) for n in ns] def soluciones(ns: list[int]) -> list[Estado]: return buscaProfundidad(sucesores, esFinal, inicial(ns)) def suma0(ns: list[int]) -> list[list[int]]: xss = [list(sorted(s[0])) for s in soluciones(ns)] r = [] for xs in xss: if xs not in r: r.append(xs) return r # Verificación # ============ def test_suma0() -> None: assert suma0([-7,-3,-2,5,8]) == \ [[-3,-2,5]] assert suma0([-7,-3,-2,5,8,-1]) == \ [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]] assert not suma0([-7,-3,1,5,8]) print("Verificado") # La verificación es # >>> test_suma0() # Verificado |
2. Problema de las jarras (mediante espacios de estados)
En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.
El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en la jarra de A litros de capacidad.
Usando el procedimiento de búsqueda en anchura, definir la función
1 |
jarras :: (Int,Int,Int) -> [[(Int,Int)]] |
tal jarras (a,b,c)
es la lista de las soluciones del problema de las jarras (a,b,c)
. Por ejemplo,
1 2 3 4 |
λ> take 3 (jarras (4,3,2)) [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)], [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)], [(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]] |
La interpretación [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)] es:
- (0,0) se inicia con las dos jarras vacías,
- (4,0) se llena la jarra de 4 con el grifo,
- (1,3) se llena la de 3 con la de 4,
- (1,0) se vacía la de 3,
- (0,1) se pasa el contenido de la primera a la segunda,
- (4,1) se llena la primera con el grifo,
- (2,3) se llena la segunda con la primera.
Otros ejemplos
1 2 3 4 5 6 |
λ> length (jarras (15,10,5)) 8 λ> map length (jarras (15,10,5)) [3,5,5,7,7,7,8,9] λ> jarras (15,10,4) [] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
module Problema_de_las_jarras where import BusquedaEnAnchura (buscaAnchura) import Test.Hspec (Spec, hspec, it, shouldBe) -- Un problema es una lista de 3 números enteros (a,b,c) tales que a es -- la capacidad de la primera jarra, b es la capacidad de la segunda -- jarra y c es el número de litros que se desea obtener en la primera -- jarra. type Problema = (Int,Int,Int) -- Una configuracion es una lista de dos números. El primero es el -- contenido de la primera jarra y el segundo el de la segunda. type Configuracion = (Int,Int) -- Inicialmente, las dos jarras están vacías. configuracionInicial :: Configuracion configuracionInicial = (0,0) -- (esConfiguracionFinal p e) se verifica si e es un configuracion final -- del problema p. esConfiguracionFinal :: Problema -> Configuracion -> Bool esConfiguracionFinal (_,_,c) (x,_) = x == c -- (sucesorasConfiguracion p c) son las sucesoras de la configuración c -- del problema p. Por ejemplo, -- sucesorasConfiguracion (4,3,2) (0,0) == [(4,0),(0,3)] -- sucesorasConfiguracion (4,3,2) (4,0) == [(4,3),(0,0),(1,3)] -- sucesorasConfiguracion (4,3,2) (4,3) == [(0,3),(4,0)] sucesorasConfiguracion :: Problema -> Configuracion -> [Configuracion] sucesorasConfiguracion (a,b,_) (x,y) = [(a,y) | x < a] ++ [(x,b) | y < b] ++ [(0,y) | x > 0] ++ [(x,0) | y > 0] ++ [(a,y-(a-x)) | x < a, y > 0, x + y > a] ++ [(x-(b-y),b) | x > 0, y < b, x + y > b] ++ [(x+y,0) | y > 0, x + y <= a] ++ [(0,x+y) | x > 0, x + y <= b] -- Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que -- c_1 es la configuración inicial y, para 2 <= i <= n, c_i es una -- sucesora de c_(i-1). type Estado = [Configuracion] -- inicial es el estado cuyo único elemento es la configuración -- inicial. inicial :: Estado inicial = [configuracionInicial] -- (esFinal p e) se verifica si e es un estado final; es decir, su -- primer elemento es una configuración final. esFinal :: Problema -> Estado -> Bool esFinal p (e:_) = esConfiguracionFinal p e -- (sucesores p e) es la lista de los sucesores del estado e en el -- problema p. Por ejemplo, -- λ> sucesores (4,3,2) [(0,0)] -- [[(4,0),(0,0)],[(0,3),(0,0)]] -- λ> sucesores (4,3,2) [(4,0),(0,0)] -- [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]] -- λ> sucesores (4,3,2) [(4,3),(4,0),(0,0)] -- [[(0,3),(4,3),(4,0),(0,0)]] sucesores :: Problema -> Estado -> [Estado] sucesores p e@(c:_) = [c':e | c' <- sucesorasConfiguracion p c, c' `notElem` e] jarras :: Problema -> [Estado] jarras p = map reverse soluciones where soluciones = buscaAnchura (sucesores p) (esFinal p) inicial -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ take 3 (jarras (4,3,2)) `shouldBe` [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)], [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)], [(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]] it "e2" $ length (jarras (15,10,5)) `shouldBe` 8 it "e3" $ map length (jarras (15,10,5)) `shouldBe` [3,5,5,7,7,7,8,9] it "e4" $ jarras (15,10,4) `shouldBe` [] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0080 seconds -- 4 examples, 0 failures |
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
from src.BusquedaEnAnchura import buscaAnchura # Un problema es una lista de 3 números enteros (a,b,c) tales que a es # la capacidad de la primera jarra, b es la capacidad de la segunda # jarra y c es el número de litros que se desea obtener en la primera # jarra. Problema = tuple[int, int, int] # Una configuracion es una lista de dos números. El primero es el # contenido de la primera jarra y el segundo el de la segunda. Configuracion = tuple[int, int] # Inicialmente, las dos jarras están vacías. configuracionInicial: Configuracion = (0,0) # esConfiguracionFinal(p, e) se verifica si e es un configuracion final # del problema p. def esConfiguracionFinal(p: Problema, c: Configuracion) -> bool: return p[2] == c[0] # sucesorasConfiguracion(p, c) son las sucesoras de la configuración c # del problema p. Por ejemplo, # sucesorasConfiguracion((4,3,2), (0,0)) == [(4,0),(0,3)] # sucesorasConfiguracion((4,3,2), (4,0)) == [(4,3),(0,0),(1,3)] # sucesorasConfiguracion((4,3,2), (4,3)) == [(0,3),(4,0)] def sucesorasConfiguracion(p: Problema, c: Configuracion) -> list[Configuracion]: (a, b, _) = p (x, y) = c r = [] if x < a: r.append((a, y)) if y < b: r.append((x, b)) if x > 0: r.append((0, y)) if y > 0: r.append((x, 0)) if x < a and y > 0 and x + y > a: r.append((a, y - (a - x))) if x > 0 and y < b and x + y > b: r.append((x - (b - y), b)) if y > 0 and x + y <= a: r.append((x + y, 0)) if x > 0 and x + y <= b: r.append((0, x + y)) return r # Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que # c_1 es la configuración inicial y, para 2 <= i <= n, c_i es una # sucesora de c_(i-1). Estado = list[Configuracion] # inicial es el estado cuyo único elemento es la configuración # inicial. inicial: Estado = [configuracionInicial] # esFinal(p, e) se verifica si e es un estado final; es decir, su # primer elemento es una configuración final. def esFinal(p: Problema, e: Estado) -> bool: return esConfiguracionFinal(p, e[0]) # sucesores(p, e) es la lista de los sucesores del estado e en el # problema p. Por ejemplo, # λ> sucesores((4,3,2), [(0,0)]) # [[(4,0),(0,0)],[(0,3),(0,0)]] # λ> sucesores((4,3,2), [(4,0),(0,0)]) # [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]] # λ> sucesores((4,3,2), [(4,3),(4,0),(0,0)]) # [[(0,3),(4,3),(4,0),(0,0)]] def sucesores(p: Problema, e: Estado) -> list[Estado]: return [[c] + e for c in sucesorasConfiguracion(p, e[0]) if c not in e] def jarras(p: Problema) -> list[Estado]: soluciones = buscaAnchura(lambda e: sucesores(p, e), lambda e: esFinal(p, e), inicial) return [list(reversed(e)) for e in soluciones] # Verificación # ============ def test_jarras() -> None: assert jarras((4,3,2))[:3] == \ [[(0, 0), (4, 0), (1, 3), (1, 0), (0, 1), (4, 1), (2, 3)], [(0, 0), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)], [(0, 0), (4, 0), (4, 3), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)]] assert len(jarras((15,10,5))) == 8 assert [len(e) for e in jarras((15,10,5))] == [3, 5, 5, 7, 7, 7, 8, 9] assert jarras((15,10,4)) == [] print("Verificado") # La verificación es # >>> test_jarras() # Verificado |
3. La función de Fibonacci por programación dinámica
Los primeros términos de la sucesión de Fibonacci son
1 |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... |
Escribir dos definiciones (una recursiva y otra con programación dinámica) de la función
1 |
fib :: Integer -> Integer |
tal que fib n
es el n
-ésimo término de la sucesión de Fibonacci. Por ejemplo,
1 |
fib 6 == 8 |
Comparar la eficiencia de las dos definiciones.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
module La_funcion_de_Fibonacci_por_programacion_dinamica where import Data.Array import Test.Hspec (Spec, hspec, it, shouldBe) -- 1ª definición (por recursión) -- ============================= fib1 :: Integer -> Integer fib1 0 = 0 fib1 1 = 1 fib1 n = fib1 (n-1) + fib1 (n-2) -- 2ª definición (con programación dinámica) -- ========================================= fib2 :: Integer -> Integer fib2 n = vectorFib2 n ! n -- (vectorFib2 n) es el vector con índices de 0 a n tal que el valor -- de la posición i es el i-ésimo número de Finonacci. Por ejemplo, -- λ> vectorFib2 7 -- array (0,7) [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13)] vectorFib2 :: Integer -> Array Integer Integer vectorFib2 n = v where v = array (0,n) [(i,f i) | i <- [0..n]] f 0 = 0 f 1 = 1 f m = v!(m-1) + v!(m-2) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> fib1 34 -- 5702887 -- (11.82 secs, 3,504,944,704 bytes) -- λ> fib2 34 -- 5702887 -- (0.01 secs, 587,808 bytes) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ fib1 6 `shouldBe` 8 it "e2" $ fib2 6 `shouldBe` 8 it "e3" $ map fib1 [0..9] `shouldBe` map fib2 [0..9] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.0007 seconds -- 3 examples, 0 failures -- (0.01 secs, 788,952 bytes) |
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
from sys import setrecursionlimit from timeit import Timer, default_timer import numpy as np import numpy.typing as npt setrecursionlimit(10**6) # 1ª definición (por recursión) # ============================= def fib1(n: int) -> int: if n == 0: return 0 if n == 1: return 1 return fib1(n - 1) + fib1(n - 2) # 2ª definición (con programación dinámica) # ========================================= def fib2(n: int) -> int: return vectorFib2(n)[n] # (vectorFib2 n) es el vector con índices de 0 a n tal que el valor # de la posición i es el i-ésimo número de Finonacci. Por ejemplo, # >>> vectorFib2(7) # [0, 1, 1, 2, 3, 5, 8, 13] def vectorFib2(n: int) -> list[int]: v = [0] * (n + 1) v[0] = 0 v[1] = 1 for i in range(2, n + 1): v[i] = v[i - 1] + v[i - 2] return v # 2ª definición (con programación dinámica y array) # ================================================= def fib3(n: int) -> int: return vectorFib3(n)[n] # (vectorFib3 n) es el vector con índices de 0 a n tal que el valor # de la posición i es el i-ésimo número de Finonacci. Por ejemplo, # >>> vectorFib3(7) # array([ 0, 1, 1, 2, 3, 5, 8, 13]) def vectorFib3(n: int) -> npt.NDArray[np.complex64]: v = np.zeros(n + 1, dtype=int) v[0] = 0 v[1] = 1 for i in range(2, n + 1): v[i] = v[i - 1] + v[i - 2] return v # 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('fib1(34)') # 2.10 segundos # >>> tiempo('fib2(34)') # 0.00 segundos # >>> tiempo('fib3(34)') # 0.00 segundos # # >>> tiempo('fib2(100000)') # 0.37 segundos # >>> tiempo('fib3(100000)') # 0.08 segundos # Verificación # ============ def test_fib() -> None: assert fib1(6) == 8 assert fib2(6) == 8 assert fib3(6) == 8 print("Verificado") # La verificación es # >>> test_fib() # Verificado |
4. Coeficientes binomiales (con programación dinámica)
El coeficiente binomial n
sobre k
es el número de subconjuntos de k
elementos escogidos de un conjunto con n
elementos.
Definir la función
1 |
binomial :: Integer -> Integer -> Integer |
tal que binomial n k
es el coeficiente binomial n
sobre k
. Por ejemplo,
1 2 3 |
binomial 6 3 == 20 binomial 5 2 == 10 binomial 5 3 == 10 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
module Coeficientes_binomiales where import Data.Array (Array, (!), array) import Test.Hspec (Spec, hspec, it, shouldBe) -- 1ª definición (por recursión) -- ============================= binomial1 :: Integer -> Integer -> Integer binomial1 _ 0 = 1 binomial1 n k | n == k = 1 | otherwise = binomial1 (n-1) (k-1) + binomial1 (n-1) k -- 2ª definición (con programación dinámica) -- ========================================= binomial2 :: Integer -> Integer -> Integer binomial2 n k = matrizBinomial2 n k ! (n,k) -- (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el -- valor en la posición (i,j) (con j <= i) es el coeficiente binomial i -- sobre j. Por ejemplo, -- λ> [[(matrizBinomial2 3 3)!(i,j) | j <- [0..i]] | i <- [0..3]] -- [[1],[1,1],[1,2,1],[1,3,3,1]] matrizBinomial2 :: Integer -> Integer -> Array (Integer,Integer) Integer matrizBinomial2 n k = q where q = array ((0,0),(n,k)) [((i,j),f i j) | i <- [0..n], j <- [0..k]] f _ 0 = 1 f i j | i == j = 1 | otherwise = q!(i-1,j-1) + q!(i-1,j) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> binomial1 25 12 -- 5200300 -- (6.45 secs, 2,654,797,776 bytes) -- λ> binomial2 25 12 -- 5200300 -- (0.00 secs, 826,272 bytes) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ binomial1 6 3 `shouldBe` 20 it "e2" $ binomial1 5 2 `shouldBe` 10 it "e3" $ binomial1 5 3 `shouldBe` 10 it "e4" $ binomial2 6 3 `shouldBe` 20 it "e5" $ binomial2 5 2 `shouldBe` 10 it "e6" $ binomial2 5 3 `shouldBe` 10 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- -- Finished in 0.0006 seconds -- 6 examples, 0 failures |
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
from sys import setrecursionlimit from timeit import Timer, default_timer import numpy as np import numpy.typing as npt setrecursionlimit(10**6) # 1ª definición (por recursión) # ============================= def binomial1(n: int, k: int) -> int: if k == 0: return 1 if n == k: return 1 return binomial1(n-1, k-1) + binomial1(n-1, k) # 2ª definición (con programación dinámica) # ========================================= def binomial2(n: int, k: int) -> int: return matrizBinomial2(n, k)[n][k] # (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el # valor en la posición (i,j) (con j <= i) es el coeficiente binomial i # sobre j. Por ejemplo, # >>> matrizBinomial2(3, 3) # [[1, 0, 0, 0], [1, 1, 0, 0], [1, 2, 1, 0], [1, 3, 3, 1]] def matrizBinomial2(n: int, k: int) -> list[list[int]]: q = [[0 for i in range(k + 1)] for j in range(n + 1)] for i in range(n + 1): for j in range(min(i, k) + 1): if j == 0: q[i][j] = 1 elif i == j: q[i][j] = 1 else: q[i][j] = q[i - 1][j - 1] + q[i - 1][j] return q # 3ª definición (con programación dinámica y numpy) # ================================================ def binomial3(n: int, k: int) -> int: return matrizBinomial3(n, k)[n][k] # (matrizBinomial3 n k) es la matriz de orden (n+1)x(k+1) tal que el # valor en la posición (i,j) (con j <= i) es el coeficiente binomial i # sobre j. Por ejemplo, # >>> matrizBinomial3(3, 3) # array([[1, 0, 0, 0], # [1, 1, 0, 0], # [1, 2, 1, 0], # [1, 3, 3, 1]]) def matrizBinomial3(n: int, k: int) -> npt.NDArray[np.int_]: q = np.zeros((n + 1, k + 1), dtype=object) for i in range(n + 1): for j in range(min(i, k) + 1): if j == 0: q[i, j] = 1 elif i == j: q[i, j] = 1 else: q[i, j] = q[i - 1, j - 1] + q[i - 1, j] 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('binomial1(27, 12)') # 4.26 segundos # >>> tiempo('binomial2(27, 12)') # 0.00 segundos # >>> tiempo('binomial3(27, 12)') # 0.00 segundos # # >>> tiempo('binomial2(50000, 12)') # 0.18 segundos # >>> tiempo('binomial3(50000, 12)') # 0.26 segundos # Verificación # ============ def test_binomial() -> None: assert binomial1(6, 3) == 20 assert binomial1(5, 2) == 10 assert binomial1(5, 3) == 10 assert binomial2(6, 3) == 20 assert binomial2(5, 2) == 10 assert binomial2(5, 3) == 10 assert binomial3(6, 3) == 20 assert binomial3(5, 2) == 10 assert binomial3(5, 3) == 10 print("Verificado") # La verificación es # >>> test_binomial() # Verificado |
5. Longitud de la subsecuencia común máxima (con programación dinámica)
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
1 |
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,
1 2 3 |
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.
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
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 |
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
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 |
6. Subsecuencia común máxima (con programación dinámica)
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
1 |
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,
1 2 3 |
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.
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
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 |
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
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 |