{"id":8288,"date":"2023-09-29T06:00:33","date_gmt":"2023-09-29T04:00:33","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8288"},"modified":"2024-05-17T18:46:34","modified_gmt":"2024-05-17T16:46:34","slug":"29-sep-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/29-sep-23\/","title":{"rendered":"Subsecuencia com\u00fan m\u00e1xima (con programaci\u00f3n din\u00e1mica)"},"content":{"rendered":"

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\u00edan originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, \u00abaaoa\u00bb es una subsecuencia de la secuencia \u00abamapola\u00bb.<\/p>\n

El t\u00e9rmino tambi\u00e9n se aplica cuando quitamos todos los elementos (es decir, la secuencia vac\u00eda es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de s\u00ed misma).<\/p>\n

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 = \u00abamapola\u00bb e Y = \u00abmatamoscas\u00bb, la secuencia \u00abaaoa\u00bb es una de las subsecuencias comunes de X e Y m\u00e1s larga, con longitud 4, ya que no hay ninguna subsecuencia com\u00fan a X e Y de longitud mayor que 4. Tambi\u00e9n son subsecuencias comunes de longitud 4 \u00abmaoa\u00bb o \u00abamoa\u00bb.<\/p>\n

Definir la funci\u00f3n<\/p>\n

\n   scm :: Eq a => [a] -> [a] -> [a]\n<\/pre>\n
tal que scm xs ys<\/code> es una de las subsecuencias comunes de longitud m\u00e1xima de xs<\/code> e ys<\/code>. Por ejemplo,<\/p>\n
\n   scm \"amapola\" \"matamoscas\" == \"amoa\"\n   scm \"atamos\" \"matamoscas\"  == \"atamos\"\n   scm \"aaa\" \"bbbb\"           == \"\"\n<\/pre>\n
<\/p>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nmodule Subsecuencia_comun_maxima where\n\nimport Data.Array (Array, (!), array, listArray)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\n-- =============================\n\nscm1 :: Eq a => [a] -> [a] -> [a]\nscm1 [] _ = []\nscm1 _ [] = []\nscm1 (x:xs) (y:ys)\n  | x == y    = x : scm1 xs ys\n  | otherwise = mayor (scm1 (x:xs) ys) (scm1 xs (y:ys))\n\n-- (mayor xs ys) es la cadena m\u00e1s larga de xs e ys.\n--    mayor \"hola\" \"buenas\"  ==  \"buenas\"\n--    mayor \"hola\" \"pera\"    ==  \"hola\"\nmayor :: [a] -> [a] -> [a]\nmayor xs ys\n  | length xs >= length ys = xs\n  | otherwise              = ys\n\n-- 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =========================================\n\nscm2 :: Eq a => [a] -> [a] -> [a]\nscm2 xs ys = reverse (matrizSCM2 xs ys ! (n,m))\n  where n = length xs\n        m = length ys\n\n-- (matrizSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n\n-- y m son los n\u00fameros de elementos de xs e ys, respectivamente) tal que\n-- el valor en la posici\u00f3n (i,j) es una SCM de los i primeros\n-- elementos de xs y los j primeros elementos de ys. Por ejemplo,\n--    \u03bb> elems (matrizSCM2 \"amapola\" \"matamoscas\")\n--    [\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\n--     \"a\",\"a\",\"a\",\"\",\"m\",\"a\",\"a\",\"a\",\"ma\",\"ma\",\"ma\",\"ma\",\"ma\",\"ma\",\"\",\n--     \"m\",\"am\",\"am\",\"aa\",\"ma\",\"ma\",\"ma\",\"ma\",\"ama\",\"ama\",\"\",\"m\",\"am\",\n--     \"am\",\"aa\",\"ma\",\"ma\",\"ma\",\"ma\",\"ama\",\"ama\",\"\",\"m\",\"am\",\"am\",\"aa\",\n--     \"ma\",\"oma\",\"oma\",\"oma\",\"ama\",\"ama\",\"\",\"m\",\"am\",\"am\",\"aa\",\"ma\",\n--     \"oma\",\"oma\",\"oma\",\"ama\",\"ama\",\"\",\"m\",\"am\",\"am\",\"aam\",\"aam\",\"oma\",\n--     \"oma\",\"oma\",\"aoma\",\"aoma\"]\n-- Gr\u00e1ficamente,\n--        m   a    t    a     m     o     s     c     a      s\n--    [\"\",\"\" ,\"\"  ,\"\"  ,\"\"   ,\"\"   ,\"\"   ,\"\"   ,\"\"   ,\"\"    ,\"\",\n-- a   \"\",\"\" ,\"a\" ,\"a\" ,\"a\"  ,\"a\"  ,\"a\"  ,\"a\"  ,\"a\"  ,\"a\"   ,\"a\",\n-- m   \"\",\"m\",\"a\" ,\"a\" ,\"a\"  ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\"  ,\"ma\",\n-- a   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ama\" ,\"ama\",\n-- p   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ama\" ,\"ama\",\n-- o   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"oma\",\"oma\",\"oma\",\"ama\" ,\"ama\",\n-- l   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"oma\",\"oma\",\"oma\",\"ama\" ,\"ama\",\n-- a   \"\",\"m\",\"am\",\"am\",\"aam\",\"aam\",\"oma\",\"oma\",\"oma\",\"aoma\",\"aoma\"]\nmatrizSCM2 :: Eq a => [a] -> [a] -> Array (Int,Int) [a]\nmatrizSCM2 xs ys = q where\n  q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]\n  n = length xs\n  m = length ys\n  v = listArray (1,n) xs\n  w = listArray (1,m) ys\n  f 0 _ = []\n  f _ 0 = []\n  f i j | v ! i == w ! j = (v!i) : (q ! (i-1,j-1))\n        | otherwise      = mayor (q ! (i-1,j)) (q ! (i,j-1))\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (scm1 (take 18 (cycle [1,3])) (take 18 (cycle [2,3])))\n--    9\n--    (20.17 secs, 11,436,759,992 bytes)\n--    \u03bb> length (scm2 (take 18 (cycle [1,3])) (take 18 (cycle [2,3])))\n--    9\n--    (0.00 secs, 1,013,624 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    scm1 \"amapola\" \"matamoscas\" `shouldBe` \"amoa\"\n  it \"e2\" $\n    scm1 \"atamos\" \"matamoscas\"  `shouldBe` \"atamos\"\n  it \"e3\" $\n    scm1 \"aaa\" \"bbbb\"           `shouldBe` \"\"\n  it \"e4\" $\n    scm2 \"amapola\" \"matamoscas\" `shouldBe` \"amoa\"\n  it \"e5\" $\n    scm2 \"atamos\" \"matamoscas\"  `shouldBe` \"atamos\"\n  it \"e6\" $\n    scm2 \"aaa\" \"bbbb\"           `shouldBe` \"\"\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--    e5\n--    e6\n--\n--    Finished in 0.0026 seconds\n--    6 examples, 0 failures\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa definici\u00f3n (por recursi\u00f3n)\n# =============================\n\n# (mayor xs ys) es la cadena m\u00e1s larga de xs e ys.\n#    mayor \"hola\" \"buenas\"  ==  \"buenas\"\n#    mayor \"hola\" \"pera\"    ==  \"hola\"\ndef mayor(xs: str, ys: str) -> str:\n    if len(xs) >= len(ys):\n        return xs\n    return ys\n\ndef scm1(xs: str, ys: str) -> str:\n    if not xs:\n        return \"\"\n    if not ys:\n        return \"\"\n    if xs[0] == ys[0]:\n        return xs[0] + scm1(xs[1:], ys[1:])\n    return mayor(scm1(xs, ys[1:]), scm1(xs[1:], ys))\n\n# 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n# =========================================\n\ndef scm2(xs: str, ys: str) -> str:\n    n = len(xs)\n    m = len(ys)\n    return (matrizSCM2(xs, ys)[n][m])[::-1]\n\n# matrizSCM2(xs, ys) es la matriz de orden (n+1)x(m+1) (donde n\n# y m son los n\u00fameros de elementos de xs e ys, respectivamente) tal que\n# el valor en la posici\u00f3n (i,j) es una SCM de los i primeros\n# elementos de xs y los j primeros elementos de ys. Por ejemplo,\n#    >>> matrizSCM2(\"amapola\", \"matamoscas\")\n#    [['', '', '', '', '', '', '', '', '', '', ''],\n#     ['', '', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'],\n#     ['', 'm', 'a', 'a', 'a', 'ma', 'ma', 'ma', 'ma', 'ma', 'ma'],\n#     ['', 'm', 'am', 'am', 'aa', 'ma', 'ma', 'ma', 'ma', 'ama', 'ama'],\n#     ['', 'm', 'am', 'am', 'aa', 'ma', 'ma', 'ma', 'ma', 'ama', 'ama'],\n#     ['', 'm', 'am', 'am', 'aa', 'ma', 'oma', 'oma', 'oma', 'ama', 'ama'],\n#     ['', 'm', 'am', 'am', 'aa', 'ma', 'oma', 'oma', 'oma', 'ama', 'ama'],\n#     ['', 'm', 'am', 'am', 'aam', 'aam', 'oma', 'oma', 'oma', 'aoma', 'aoma']]\n# Gr\u00e1ficamente,\n#        m   a    t    a     m     o     s     c     a      s\n#    [\"\",\"\" ,\"\"  ,\"\"  ,\"\"   ,\"\"   ,\"\"   ,\"\"   ,\"\"   ,\"\"    ,\"\",\n# a   \"\",\"\" ,\"a\" ,\"a\" ,\"a\"  ,\"a\"  ,\"a\"  ,\"a\"  ,\"a\"  ,\"a\"   ,\"a\",\n# m   \"\",\"m\",\"a\" ,\"a\" ,\"a\"  ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\"  ,\"ma\",\n# a   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ama\" ,\"ama\",\n# p   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ma\" ,\"ama\" ,\"ama\",\n# o   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"oma\",\"oma\",\"oma\",\"ama\" ,\"ama\",\n# l   \"\",\"m\",\"am\",\"am\",\"aa\" ,\"ma\" ,\"oma\",\"oma\",\"oma\",\"ama\" ,\"ama\",\n# a   \"\",\"m\",\"am\",\"am\",\"aam\",\"aam\",\"oma\",\"oma\",\"oma\",\"aoma\",\"aoma\"]\ndef matrizSCM2(xs: str, ys: str) -> list[list[str]]:\n    n = len(xs)\n    m = len(ys)\n    q = [[\"\" for _ in range(m + 1)] for _ in range(n + 1)]\n    for i in range(1, n + 1):\n        for j in range(1, m + 1):\n            if xs[i - 1] == ys[j - 1]:\n                q[i][j] = xs[i - 1] + q[i - 1][j - 1]\n            else:\n                q[i][j] = mayor(q[i - 1][j], q[i][j - 1])\n    return q\n\n# # Comparaci\u00f3n de eficiencia\n# # =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('scm1([\"1\",\"3\"]*9, [\"2\",\"3\"]*9)')\n#    8.44 segundos\n#    >>> tiempo('scm2([\"1\",\"3\"]*9, [\"2\",\"3\"]*9)')\n#    0.00 segundos\n\n# Verificaci\u00f3n\n# ============\n\ndef test_scm() -> None:\n    assert scm1(\"amapola\", \"matamoscas\") == \"amoa\"\n    assert scm1(\"atamos\", \"matamoscas\")  == \"atamos\"\n    assert scm1(\"aaa\", \"bbbb\")           == \"\"\n    assert scm2(\"amapola\", \"matamoscas\") == \"amoa\"\n    assert scm2(\"atamos\", \"matamoscas\")  == \"atamos\"\n    assert scm2(\"aaa\", \"bbbb\")           == \"\"\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_scm()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
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\u00edan originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, \u00abaaoa\u00bb es una subsecuencia de la secuencia \u00abamapola\u00bb. El t\u00e9rmino tambi\u00e9n se aplica cuando quitamos todos…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[591],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8288"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8288"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8288\/revisions"}],"predecessor-version":[{"id":8576,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8288\/revisions\/8576"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8288"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8288"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8288"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}