{"id":8370,"date":"2024-01-09T12:14:08","date_gmt":"2024-01-09T10:14:08","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8370"},"modified":"2024-02-02T17:07:16","modified_gmt":"2024-02-02T15:07:16","slug":"09-ene-24","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/09-ene-24\/","title":{"rendered":"La serie de Thue-Morse"},"content":{"rendered":"

La serie de Thue-Morse<\/a> comienza con el t\u00e9rmino [0] y sus siguientes t\u00e9rminos se construyen a\u00f1adi\u00e9ndole al anterior su complementario (es decir, la lista obtenida cambiando el 0 por 1 y el 1 por 0). Los primeros t\u00e9rminos de la serie son<\/p>\n

\n   [0]\n   [0,1]\n   [0,1,1,0]\n   [0,1,1,0,1,0,0,1]\n   [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]\n<\/pre>\n
Definir la lista<\/p>\n
\n   serieThueMorse :: [[Int]]\n<\/pre>\n
tal que sus elementos son los t\u00e9rminos de la serie de Thue-Morse. Por ejemplo,<\/p>\n
\n   \u03bb> take 4 serieThueMorse\n   [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]\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 La_serie_de_Thue_Morse where\n\nimport Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nserieThueMorse1 :: [[Int]]\nserieThueMorse1 = map termSerieThueMorse [0..]\n\n-- (termSerieThueMorse n) es el t\u00e9rmino n-\u00e9simo de la serie de\n-- Thue-Morse. Por ejemplo,\n--    termSerieThueMorse 1  ==  [0,1]\n--    termSerieThueMorse 2  ==  [0,1,1,0]\n--    termSerieThueMorse 3  ==  [0,1,1,0,1,0,0,1]\n--    termSerieThueMorse 4  ==  [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]\ntermSerieThueMorse :: Int -> [Int]\ntermSerieThueMorse 0 = [0]\ntermSerieThueMorse n = xs ++ complementaria xs\n  where xs = termSerieThueMorse (n-1)\n\n-- (complementaria xs) es la complementaria de la lista xs (formada por\n-- ceros y unos); es decir, la lista obtenida cambiando el 0 por 1 y el\n-- 1 por 0. Por ejemplo,\n--    complementaria [1,0,0,1,1,0,1]  ==  [0,1,1,0,0,1,0]\ncomplementaria :: [Int] -> [Int]\ncomplementaria = map (1-)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nserieThueMorse2 :: [[Int]]\nserieThueMorse2 = [0] : map paso serieThueMorse2\n  where paso xs = xs ++ complementaria xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nserieThueMorse3 :: [[Int]]\nserieThueMorse3 = iterate paso [0]\n  where paso xs = xs ++ complementaria xs\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\n-- Observando que cada t\u00e9rmino de la serie de Thue-Morse se obtiene del\n-- anterior sustituyendo los 1 por 1, 0 y los 0 por  0, 1.\n\nserieThueMorse4 :: [[Int]]\nserieThueMorse4 = [0] : map (concatMap paso4) serieThueMorse4\n  where paso4 x = [x,1-x]\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: [[Int]] -> Spec\nspecG serieThueMorse = do\n  it \"e1\" $\n    take 4 serieThueMorse `shouldBe`\n    [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]\n\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG serieThueMorse1\n  describe \"def. 2\" $ specG serieThueMorse2\n  describe \"def. 3\" $ specG serieThueMorse3\n  describe \"def. 4\" $ specG serieThueMorse4\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    4 examples, 0 failures\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_serieThueMorse :: NonNegative Int -> Bool\nprop_serieThueMorse  (NonNegative n) =\n  all (== serieThueMorse1 !! n)\n      [serieThueMorse2 !! n,\n       serieThueMorse3 !! n,\n       serieThueMorse4 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=20}) prop_serieThueMorse\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> (serieThueMorse1 !! 23) !! (2^22)\n--    1\n--    (1.08 secs, 839,419,224 bytes)\n--    \u03bb> (serieThueMorse2 !! 23) !! (2^22)\n--    1\n--    (0.61 secs, 839,413,592 bytes)\n--    \u03bb> (serieThueMorse3 !! 23) !! (2^22)\n--    1\n--    (1.43 secs, 839,413,592 bytes)\n--    \u03bb> (serieThueMorse4 !! 23) !! (2^22)\n--    1\n--    (1.57 secs, 1,007,190,024 bytes)\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom itertools import count, islice\nfrom typing import Iterator\n\n# Soluci\u00f3n\n# ========\n\n# complementaria(xs) es la complementaria de la lista xs (formada por\n# ceros y unos); es decir, la lista obtenida cambiando el 0 por 1 y el\n# 1 por 0. Por ejemplo,\n#    complementaria([1,0,0,1,1,0,1])  ==  [0,1,1,0,0,1,0]\ndef complementaria(xs: list[int]) -> list[int]:\n    return [1 - x for x in xs]\n\n# termSerieThueMorse(n) es el t\u00e9rmino n-\u00e9simo de la serie de\n# Thue-Morse. Por ejemplo,\n#    termSerieThueMorse(1)  ==  [0,1]\n#    termSerieThueMorse(2)  ==  [0,1,1,0]\n#    termSerieThueMorse(3)  ==  [0,1,1,0,1,0,0,1]\n#    termSerieThueMorse(4)  ==  [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]\ndef termSerieThueMorse(n: int) -> list[int]:\n    if n == 0:\n        return [0]\n    xs = termSerieThueMorse(n-1)\n    return xs + complementaria(xs)\n\ndef serieThueMorse() -> Iterator[list[int]]:\n    return (termSerieThueMorse(n) for n in count())\n\n# Verificaci\u00f3n\n# ============\n\ndef test_serieThueMorse() -> None:\n    assert list(islice(serieThueMorse(), 4)) == \\\n        [[0], [0, 1], [0, 1, 1, 0], [0, 1, 1, 0, 1, 0, 0, 1]]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_serieThueMorse()\n#    Verificado\n<\/pre>\n
Referencias<\/b><\/p>\n