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

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\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 com\u00fan 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

Se desea encontrar la longitud de las subsecuencias comunes m\u00e1s largas de dos secuencias de caracteres dadas.<\/p>\n

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

\n   longitudSCM :: Eq a => [a] -> [a] -> Int\n<\/pre>\n
tal que longitudSCM xs ys<\/code> es la longitud de la subsecuencia m\u00e1xima de xs<\/code> e ys<\/code>. Por ejemplo,<\/p>\n
\n   longitudSCM \"amapola\" \"matamoscas\" == 4\n   longitudSCM \"atamos\" \"matamoscas\"  == 6\n   longitudSCM \"aaa\" \"bbbb\"           == 0\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 Longitud_SCM 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\nlongitudSCM1 :: Eq a => [a] -> [a] -> Int\nlongitudSCM1 [] _ = 0\nlongitudSCM1 _ [] = 0\nlongitudSCM1 (x:xs) (y:ys)\n  | x == y    = 1 + longitudSCM1 xs ys\n  | otherwise = max (longitudSCM1 (x:xs) ys) (longitudSCM1 xs (y:ys))\n\n-- 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =========================================\n\nlongitudSCM2 :: Eq a => [a] -> [a] -> Int\nlongitudSCM2 xs ys = matrizLongitudSCM2 xs ys ! (n,m)\n  where n = length xs\n        m = length ys\n\n-- (matrizLongitudSCM2 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 la longitud de la SCM de los i\n-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,\n--    \u03bb> elems (matrizLongitudSCM2 \"amapola\" \"matamoscas\")\n--    [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,\n--     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,\n--     0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4]\n-- Gr\u00e1ficamente,\n--       m a t a m o s c a s\n--    [0,0,0,0,0,0,0,0,0,0,0,\n-- a   0,0,1,1,1,1,1,1,1,1,1,\n-- m   0,1,1,1,1,2,2,2,2,2,2,\n-- a   0,1,2,2,2,2,2,2,2,3,3,\n-- p   0,1,2,2,2,2,2,2,2,3,3,\n-- o   0,1,2,2,2,2,3,3,3,3,3,\n-- l   0,1,2,2,2,2,3,3,3,3,3,\n-- a   0,1,2,2,3,3,3,3,3,4,4]\nmatrizLongitudSCM2 :: Eq a => [a] -> [a] -> Array (Int,Int) Int\nmatrizLongitudSCM2 xs ys = q\n  where\n    n = length xs\n    m = length ys\n    v = listArray (1,n) xs\n    w = listArray (1,m) ys\n    q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]\n      where f 0 _ = 0\n            f _ 0 = 0\n            f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)\n                  | otherwise      = max (q ! (i-1,j)) (q ! (i,j-1))\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> longitudSCM1 (take 18 (cycle [1,3])) (take 18 (cycle [2,3]))\n--    9\n--    (13.90 secs, 8,883,660,048 bytes)\n--    \u03bb> longitudSCM2 (take 18 (cycle [1,3])) (take 18 (cycle [2,3]))\n--    9\n--    (0.01 secs, 953,880 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    longitudSCM1 \"amapola\" \"matamoscas\" `shouldBe` 4\n  it \"e2\" $\n    longitudSCM1 \"atamos\" \"matamoscas\"  `shouldBe` 6\n  it \"e3\" $\n    longitudSCM1 \"aaa\" \"bbbb\"           `shouldBe` 0\n  it \"e4\" $\n    longitudSCM2 \"amapola\" \"matamoscas\" `shouldBe` 4\n  it \"e5\" $\n    longitudSCM2 \"atamos\" \"matamoscas\"  `shouldBe` 6\n  it \"e6\" $\n    longitudSCM2 \"aaa\" \"bbbb\"           `shouldBe` 0\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.0025 seconds\n--    6 examples, 0 failures\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom timeit import Timer, default_timer\n\n# 1\u00aa definici\u00f3n (por recursi\u00f3n)\n# =============================\n\ndef longitudSCM1(xs: str, ys: str) -> int:\n    if not xs:\n        return 0\n    if not ys:\n        return 0\n    if xs[0] == ys[0]:\n        return 1 + longitudSCM1(xs[1:], ys[1:])\n    return max(longitudSCM1(xs, ys[1:]), longitudSCM1(xs[1:], ys))\n\n# 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n# =========================================\n\ndef longitudSCM2(xs: str, ys: str) -> int:\n    n = len(xs)\n    m = len(ys)\n    return matrizLongitudSCM2(xs, ys)[n][m]\n\n# matrizLongitudSCM2(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 la longitud de la SCM de los i\n# primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,\n#    >>> matrizLongitudSCM2(\"amapola\", \"matamoscas\")\n#    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n#     [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],\n#     [0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2],\n#     [0, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3],\n#     [0, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3],\n#     [0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3],\n#     [0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3],\n#     [0, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4]]\n#    # Gr\u00e1ficamente,\n#       m a t a m o s c a s\n#    [0,0,0,0,0,0,0,0,0,0,0,\n# a   0,0,1,1,1,1,1,1,1,1,1,\n# m   0,1,1,1,1,2,2,2,2,2,2,\n# a   0,1,2,2,2,2,2,2,2,3,3,\n# p   0,1,2,2,2,2,2,2,2,3,3,\n# o   0,1,2,2,2,2,3,3,3,3,3,\n# l   0,1,2,2,2,2,3,3,3,3,3,\n# a   0,1,2,2,3,3,3,3,3,4,4]\ndef matrizLongitudSCM2(xs: str, ys: str) -> list[list[int]]:\n    n = len(xs)\n    m = len(ys)\n    q = [[0 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] = 1 + q[i - 1][j - 1]\n            else:\n                q[i][j] = max(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('longitudSCM1([1,3]*9, [2,3]*9)')\n#    8.04 segundos\n#    >>> tiempo('longitudSCM2([1,3]*9, [2,3]*9)')\n#    0.00 segundos\n\n# Verificaci\u00f3n\n# ============\n\ndef test_longitudSCM() -> None:\n    assert longitudSCM1(\"amapola\", \"matamoscas\") == 4\n    assert longitudSCM1(\"atamos\", \"matamoscas\")  == 6\n    assert longitudSCM1(\"aaa\", \"bbbb\")           == 0\n    assert longitudSCM2(\"amapola\", \"matamoscas\") == 4\n    assert longitudSCM2(\"atamos\", \"matamoscas\")  == 6\n    assert longitudSCM2(\"aaa\", \"bbbb\")           == 0\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_longitudSCM()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
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\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…<\/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\/8286"}],"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=8286"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8286\/revisions"}],"predecessor-version":[{"id":8577,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8286\/revisions\/8577"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8286"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8286"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8286"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}