Menu Close

Autor: José A. Alonso

Longitud de la subsecuencia común máxima

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 →

Coeficientes binomiales

José A. Alonso, ,

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

   binomial :: Integer -> Integer -> Integer

tal que binomial n k es el coeficiente binomial n sobre k. Por ejemplo,

   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.


Soluciones en Haskell

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


Soluciones en Python

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
Leer más →

La función de Fibonacci por programación dinámica

José A. Alonso, ,

Los primeros términos de la sucesión de Fibonacci son

   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

   fib :: Integer -> Integer

tal que fib n es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,

   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.


Soluciones en Haskell

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)


Soluciones en Python

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
Leer más →

Problema de las jarras

José A. Alonso, ,

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

   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,

   λ> 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

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


Soluciones en Haskell

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


Soluciones en Python

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
Leer más →

Problema de suma cero

José A. Alonso, ,

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

   suma0 :: [Int] -> [[Int]]

tal que suma0 ns es la lista de las soluciones del problema de suma cero para ns. Por ejemplo,

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


Soluciones en Haskell

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


Soluciones en Python

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
Leer más →