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

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

moviéndose en cada paso una casilla hacia la derecha o abajo, son los siguientes:

Definir la función

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,

Soluciones

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


Soluciones en Haskell


Soluciones en Python

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

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:

Definir la función

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,

Soluciones

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


Soluciones en Haskell


Soluciones en Python

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

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:

Definir la función

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

Soluciones

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


Soluciones en Haskell


Soluciones en Python

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

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

Soluciones

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


Soluciones en Haskell


Soluciones en Python

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

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

Soluciones

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


Soluciones en Haskell


Soluciones en Python