La serie de Thue-Morse
La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario (es decir, la lista obtenida cambiando el 0 por 1 y el 1 por 0). Los primeros términos de la serie son
|
1 2 3 4 5 |
[0] [0,1] [0,1,1,0] [0,1,1,0,1,0,0,1] [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0] |
Definir la lista
|
1 |
serieThueMorse :: [[Int]] |
tal que sus elementos son los términos de la serie de Thue-Morse. Por ejemplo,
|
1 2 |
λ> take 4 serieThueMorse [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
module La_serie_de_Thue_Morse where import Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs) import Test.Hspec (Spec, describe, hspec, it, shouldBe) -- 1ª solución -- =========== serieThueMorse1 :: [[Int]] serieThueMorse1 = map termSerieThueMorse [0..] -- (termSerieThueMorse n) es el término n-ésimo de la serie de -- Thue-Morse. Por ejemplo, -- termSerieThueMorse 1 == [0,1] -- termSerieThueMorse 2 == [0,1,1,0] -- termSerieThueMorse 3 == [0,1,1,0,1,0,0,1] -- termSerieThueMorse 4 == [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0] termSerieThueMorse :: Int -> [Int] termSerieThueMorse 0 = [0] termSerieThueMorse n = xs ++ complementaria xs where xs = termSerieThueMorse (n-1) -- (complementaria xs) es la complementaria de la lista xs (formada por -- ceros y unos); es decir, la lista obtenida cambiando el 0 por 1 y el -- 1 por 0. Por ejemplo, -- complementaria [1,0,0,1,1,0,1] == [0,1,1,0,0,1,0] complementaria :: [Int] -> [Int] complementaria = map (1-) -- 2ª solución -- =========== serieThueMorse2 :: [[Int]] serieThueMorse2 = [0] : map paso serieThueMorse2 where paso xs = xs ++ complementaria xs -- 3ª solución -- =========== serieThueMorse3 :: [[Int]] serieThueMorse3 = iterate paso [0] where paso xs = xs ++ complementaria xs -- 4ª solución -- =========== -- Observando que cada término de la serie de Thue-Morse se obtiene del -- anterior sustituyendo los 1 por 1, 0 y los 0 por 0, 1. serieThueMorse4 :: [[Int]] serieThueMorse4 = [0] : map (concatMap paso4) serieThueMorse4 where paso4 x = [x,1-x] -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: [[Int]] -> Spec specG serieThueMorse = do it "e1" $ take 4 serieThueMorse `shouldBe` [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]] spec :: Spec spec = do describe "def. 1" $ specG serieThueMorse1 describe "def. 2" $ specG serieThueMorse2 describe "def. 3" $ specG serieThueMorse3 describe "def. 4" $ specG serieThueMorse4 -- La verificación es -- λ> verifica -- -- 4 examples, 0 failures -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_serieThueMorse :: NonNegative Int -> Bool prop_serieThueMorse (NonNegative n) = all (== serieThueMorse1 !! n) [serieThueMorse2 !! n, serieThueMorse3 !! n, serieThueMorse4 !! n] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_serieThueMorse -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> (serieThueMorse1 !! 23) !! (2^22) -- 1 -- (1.08 secs, 839,419,224 bytes) -- λ> (serieThueMorse2 !! 23) !! (2^22) -- 1 -- (0.61 secs, 839,413,592 bytes) -- λ> (serieThueMorse3 !! 23) !! (2^22) -- 1 -- (1.43 secs, 839,413,592 bytes) -- λ> (serieThueMorse4 !! 23) !! (2^22) -- 1 -- (1.57 secs, 1,007,190,024 bytes) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
from itertools import count, islice from typing import Iterator # Solución # ======== # complementaria(xs) es la complementaria de la lista xs (formada por # ceros y unos); es decir, la lista obtenida cambiando el 0 por 1 y el # 1 por 0. Por ejemplo, # complementaria([1,0,0,1,1,0,1]) == [0,1,1,0,0,1,0] def complementaria(xs: list[int]) -> list[int]: return [1 - x for x in xs] # termSerieThueMorse(n) es el término n-ésimo de la serie de # Thue-Morse. Por ejemplo, # termSerieThueMorse(1) == [0,1] # termSerieThueMorse(2) == [0,1,1,0] # termSerieThueMorse(3) == [0,1,1,0,1,0,0,1] # termSerieThueMorse(4) == [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0] def termSerieThueMorse(n: int) -> list[int]: if n == 0: return [0] xs = termSerieThueMorse(n-1) return xs + complementaria(xs) def serieThueMorse() -> Iterator[list[int]]: return (termSerieThueMorse(n) for n in count()) # Verificación # ============ def test_serieThueMorse() -> None: assert list(islice(serieThueMorse(), 4)) == \ [[0], [0, 1], [0, 1, 1, 0], [0, 1, 1, 0, 1, 0, 0, 1]] print("Verificado") # La verificación es # >>> test_serieThueMorse() # Verificado |
Referencias
- N.J.A. Sloane Sucesión A010060 en OEIS.
- Programming Praxis: Thue-Morse sequence.
- Wikipedia: Thue–Morse sequence.