Coverage for local/lib/python2.7/site-packages/sage/combinat/words/word

ValueError: The hypothesis of the algorithm used is not satisfied: the image of the 3-th letter (=b) under the 3-th morphism (=a->cd, b->dc) should start with the 2-th letter (=c).

Two examples of infinite `s`-adic words::

sage: tm = WordMorphism('a->ab,b->ba')

sage: fib = WordMorphism('a->ab,b->a')

sage: from itertools import repeat

sage: Word(words._s_adic_iterator(repeat(tm),repeat('a')))

word: abbabaabbaababbabaababbaabbabaabbaababba...

sage: Word(words._s_adic_iterator(repeat(fib),repeat('a')))

word: abaababaabaababaababaabaababaabaababaaba...

A less trivial infinite `s`-adic word::

sage: m = WordMorphism({4:tm,5:fib})

sage: tmword = words.ThueMorseWord([4,5])

sage: w = m(tmword)

sage: Word(words._s_adic_iterator(w, repeat('a')))

word: abbaababbaabbaabbaababbaababbaabbaababba...

The morphism `\sigma: a \mapsto ba, b \mapsto b` cannot satisfy the

hypothesis of the algorithm (nested prefixes)::

sage: sigma = WordMorphism('a->ba,b->b')

sage: Word(words._s_adic_iterator(repeat(sigma),repeat('a')))

Traceback (most recent call last):

...

ValueError: The hypothesis of the algorithm used is not satisfied: the image of the 2-th letter (=a) under the 2-th morphism (=a->ba, b->b) should start with the 1-th letter (=a).

AUTHORS:

- Sebastien Labbe (2009-12-18): initial version

"""

from itertools import tee

from builtins import zip

sequence_it,sequence = tee(sequence)

m = next(sequence_it)

codomain = m.codomain()

p = codomain.identity_morphism()

letters_it,letters = tee(letters)

precedent_letter = m(next(letters_it))[0]

yield precedent_letter

for (i,(m,a)) in enumerate(zip(sequence, letters)):

if not precedent_letter == m(a)[0]:

raise ValueError("The hypothesis of the algorithm used is not satisfied: the image of the %s-th letter (=%s) under the %s-th morphism (=%s) should start with the %s-th letter (=%s)."%(i+1,a,i+1,m,i,precedent_letter))

w = p(m(a)[1:])

for b in w:

yield b

p = p * m

precedent_letter = a

def s_adic(self, sequence, letters, morphisms=None):

r"""

Returns the `s`-adic infinite word obtained from a sequence of

morphisms applied on a letter.

DEFINITION (from [Fogg]_):

Let `w` be a infinite word over an alphabet `A = A_0`. A

standard representation of `w` is obtained from a sequence of

substitutions `\sigma_k : A_{k+1} \to A_k` and a sequence of letters

`a_k \in A_k` such that:

.. MATH::

\lim_{k\to\infty} \sigma_0 \circ \sigma_1 \circ \cdots

\sigma_k(a_k).

Given a set of substitutions `S`, we say that the representation is

`S`-adic standard if the substitutions are chosen in `S`.

INPUT:

- ``sequence`` - An iterable sequence of indices or of morphisms. It

may be finite or infinite. If ``sequence`` is infinite, the image

of the `(i+1)`-th letter under the `(i+1)`-th morphism must start

with the `i`-th letter.

- ``letters`` - A letter or a sequence of letters.

- ``morphisms`` - dict, list, callable or ``None`` (optional, default

``None``) an object that maps indices to morphisms. If ``None``, then

``sequence`` must consist of morphisms.

OUTPUT:

A word.

EXAMPLES:

Let's define three morphisms and compute the first nested succesive

prefixes of the `s`-adic word::

sage: m1 = WordMorphism('e->gh,f->hg')

sage: m2 = WordMorphism('c->ef,d->e')

sage: m3 = WordMorphism('a->cd,b->dc')

sage: words.s_adic([m1],'e')

word: gh

sage: words.s_adic([m1,m2],'ec')

word: ghhg

sage: words.s_adic([m1,m2,m3],'eca')

word: ghhggh

When the given sequence of morphism is finite, one may simply give

the last letter, i.e. ``'a'``, instead of giving all of them,

i.e. ``'eca'``::

sage: words.s_adic([m1,m2,m3],'a')

word: ghhggh

sage: words.s_adic([m1,m2,m3],'b')

word: ghghhg

If the letters don't satisfy the hypothesis of the algorithm

(nested prefixes), an error is raised::

sage: words.s_adic([m1,m2,m3],'ecb')

Traceback (most recent call last):

...

ValueError: The hypothesis of the algorithm used is not satisfied: the image of the 3-th letter (=b) under the 3-th morphism (=a->cd, b->dc) should start with the 2-th letter (=c).

Let's define the Thue-Morse morphism and the Fibonacci morphism

which will be used below to illustrate more examples and let's import

the ``repeat`` tool from the ``itertools``::

sage: tm = WordMorphism('a->ab,b->ba')

sage: fib = WordMorphism('a->ab,b->a')

sage: from itertools import repeat

Two trivial examples of infinite `s`-adic words::

sage: words.s_adic(repeat(tm),repeat('a'))

word: abbabaabbaababbabaababbaabbabaabbaababba...

sage: words.s_adic(repeat(fib),repeat('a'))

word: abaababaabaababaababaabaababaabaababaaba...

A less trivial infinite `s`-adic word::

sage: t = words.ThueMorseWord([tm,fib])

sage: words.s_adic(t, repeat('a'))

word: abbaababbaabbaabbaababbaababbaabbaababba...

The same thing using a sequence of indices::

sage: tmword = words.ThueMorseWord([0,1])

sage: words.s_adic(tmword, repeat('a'), [tm,fib])

word: abbaababbaabbaabbaababbaababbaabbaababba...

The correspondance of the indices may be given as a dict::

sage: words.s_adic(tmword, repeat('a'), {0:tm,1:fib})

word: abbaababbaabbaabbaababbaababbaabbaababba...

because dict are more versatile for indices::

sage: tmwordTF = words.ThueMorseWord('TF')

sage: words.s_adic(tmwordTF, repeat('a'), {'T':tm,'F':fib})

word: abbaababbaabbaabbaababbaababbaabbaababba...

or by a callable::

sage: f = lambda n: tm if n == 0 else fib

sage: words.s_adic(words.ThueMorseWord(), repeat('a'), f)

word: abbaababbaabbaabbaababbaababbaabbaababba...

Random infinite `s`-adic words::

sage: from sage.misc.prandom import randint

sage: def it():

....: while True: yield randint(0,1)

sage: words.s_adic(it(), repeat('a'), [tm,fib])

word: abbaabababbaababbaabbaababbaabababbaabba...

sage: words.s_adic(it(), repeat('a'), [tm,fib])

word: abbaababbaabbaababbaababbaabbaababbaabba...

sage: words.s_adic(it(), repeat('a'), [tm,fib])

word: abaaababaabaabaaababaabaaababaaababaabaa...

An example where the sequences cycle on two morphisms and two

letters::

sage: G = WordMorphism('a->cd,b->dc')

sage: H = WordMorphism('c->ab,d->ba')

sage: from itertools import cycle

sage: words.s_adic([G,H],'ac')

word: cddc

sage: words.s_adic(cycle([G,H]),cycle('ac'))

word: cddcdccddccdcddcdccdcddccddcdccddccdcddc...

The morphism `\sigma: a\mapsto ba, b\mapsto b` can't satisfy the

hypothesis of the nested prefixes, but one may compute arbitrarily

long finite words having the limit `\sigma^\omega(a)`::

sage: sigma = WordMorphism('a->ba,b->b')

sage: words.s_adic(repeat(sigma),repeat('a'))

Traceback (most recent call last):

...

ValueError: The hypothesis of the algorithm used is not satisfied: the image of the 2-th letter (=a) under the 2-th morphism (=a->ba, b->b) should start with the 1-th letter (=a).

sage: words.s_adic([sigma],'a')

word: ba

sage: words.s_adic([sigma,sigma],'a')

word: bba

sage: words.s_adic([sigma]*3,'a')

word: bbba

sage: words.s_adic([sigma]*4,'a')

word: bbbba

sage: words.s_adic([sigma]*5,'a')

word: bbbbba

sage: words.s_adic([sigma]*6,'a')

word: bbbbbba

sage: words.s_adic([sigma]*7,'a')

word: bbbbbbba

The following examples illustrates an `S`-adic word defined over an

infinite set `S` of morphisms `x_h`::

sage: x = lambda h:WordMorphism({1:[2],2:[3]+[1]*(h+1),3:[3]+[1]*h})

sage: for h in [0,1,2,3]:

....: print("{} {}".format(h, x(h)))

0 1->2, 2->31, 3->3

1 1->2, 2->311, 3->31

2 1->2, 2->3111, 3->311

3 1->2, 2->31111, 3->3111

sage: w = Word(lambda n : valuation(n+1, 2) ); w

word: 0102010301020104010201030102010501020103...

sage: s = words.s_adic(w, repeat(3), x); s

word: 3232232232322322322323223223232232232232...

sage: prefixe = s[:10000]

sage: list(map(prefixe.number_of_factors, range(15)))

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

sage: [_[i+1] - _[i] for i in range(len(_)-1)]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

TESTS::

sage: tm = WordMorphism('a->ab,b->ba')

sage: fib = WordMorphism('a->ab,b->a')

sage: w = words.s_adic([fib,tm,tm,fib,tm,fib]*3,'a')

sage: w

word: abaaabaababaabaaababaaababaaabaababaabaa...

sage: w.length()

32400

sage: w.parent()

Finite words over {'a', 'b'}

sage: type(w)

sage: words.s_adic([fib,tm,tm,fib,tm,fib],'aaaaaaa')

word: abaaabaababaabaaababaaababaaabaababa

sage: words.s_adic([0,1,0,1,0,1,0,1],'a',[tm,fib])

word: abbaabababbaabbaababbaababbaabababbaabba...

sage: words.s_adic([fib,fib],'bb')

Traceback (most recent call last):

...

ValueError: The hypothesis of the algorithm used is not satisfied: the image of the 2-th letter (=b) under the 2-th morphism (=a->ab, b->a) should start with the 1-th letter (=b).

Test on different letters::

sage: tm = WordMorphism({0:[0,1], 1:[1,0]})

sage: fib = WordMorphism({0:[0,1], 1:[0]})

sage: f = lambda n: tm if n == 0 else fib

sage: words.s_adic(words.ThueMorseWord(), repeat(0), f)

word: 0110010110011001100101100101100110010110...

Testing the message error for the third argument::

sage: words.s_adic(words.ThueMorseWord(), repeat(0), 5)

Traceback (most recent call last):

...

TypeError: morphisms (=5) must be None, callable or provide a __getitem__ method.

AUTHORS:

- Sebastien Labbe (2009-12-18): initial version

"""

if morphisms is None:

seq = sequence

elif hasattr(morphisms, '__getitem__'):

seq = (morphisms[i] for i in sequence)

elif hasattr(morphisms, '__call__'):

seq = (morphisms(i) for i in sequence)

else:

raise TypeError("morphisms (=%s) must be None, callable or provide a __getitem__ method."%morphisms)

from sage.combinat.words.word import FiniteWord_class

if isinstance(sequence,(tuple,list,str,FiniteWord_class)) \

and hasattr(letters, "__len__") and len(letters) == 1:

from sage.misc.all import prod

return prod(seq)(letters)

from itertools import tee

seq_it,seq= tee(seq)

m = next(seq_it)

W = m.codomain()

kwds = {}

kwds['data'] = self._s_adic_iterator(seq,letters)

kwds['datatype'] = 'iter'

kwds['caching'] = True

#kwds['check'] = False

return W.shift()(**kwds)

def PalindromicDefectWord(self, k=1, alphabet='ab'):

r"""

Return the finite word `w = a b^k a b^{k-1} a a b^{k-1} a b^{k} a`.

As described by Brlek, Hamel, Nivat and Reutenauer in [BHNR04]_, this

finite word `w` is such that the infinite periodic word `w^{\omega}`

has palindromic defect ``k``.

INPUT:

- ``k`` -- positive integer (optional, default: 1)

- ``alphabet`` -- iterable (optional, default: ``'ab'``) of size two

OUTPUT:

finite word

EXAMPLES::

sage: words.PalindromicDefectWord(10)

word: abbbbbbbbbbabbbbbbbbbaabbbbbbbbbabbbbbbb...

sage: w = words.PalindromicDefectWord(3)

sage: w

word: abbbabbaabbabbba

sage: w.defect()

sage: (w^2).defect()

sage: (w^3).defect()

On other alphabets::

sage: words.PalindromicDefectWord(3, alphabet='cd')

word: cdddcddccddcdddc

sage: words.PalindromicDefectWord(3, alphabet=['c', 3])

word: c333c33cc33c333c

TESTS::

sage: k = 25

sage: (words.PalindromicDefectWord(k)^2).defect()

If k is negative or zero, then we get the same word::

sage: words.PalindromicDefectWord(0)

word: aaaaaa

sage: words.PalindromicDefectWord(-3)

word: aaaaaa

"""

kk = k-1

a, b = alphabet

if not (isinstance(a, str) and isinstance(b, str)):

a, b = (a,), (b,)

w = a + b*k + a + b*kk + a + a + b*kk + a + b*k + a

return FiniteWords(alphabet)(w)

def BaumSweetWord(self):

r"""

Returns the Baum-Sweet Word.

The Baum-Sweet Sequence is an infinite word over the alphabet `\{0,1\}`

defined by the following string substitution rules:

`00 \rightarrow 0000`

`01 \rightarrow 1001`

`10 \rightarrow 0100`

`11 \rightarrow 1101`

The substitution rule above can be considered as a morphism on the

submonoid of `\{0,1\}` generated by `\{00,01,10,11\}` (which is a free

monoid on these generators).

It is also defined as the concatenation of the terms from the Baum-Sweet

Sequence:

.. MATH::

b_n = \begin{cases}

0, & \text{if } n = 0 \\

1, & \text{if } m \text{ is even} \\

b_{\frac{m-1}{2}}, & \text{if } m \text{ is odd}

\end{cases}

where `n=m4^k` and `m` is not divisible by 4 if `m \neq 0`.

The individual terms of the Baum-Sweet Sequence are also given by:

.. MATH::

b_n = \begin{cases}

1, & \text{if the binary representation of} n \text{ contains no block of consecutive 0's of odd length}\\

0, & \text{otherwise}\\

\end{cases}\\

for `n > 0` with `b_0 = 1`.

For more information see:

:wikipedia:`Baum-Sweet_sequence`.

EXAMPLES:

Baum-Sweet Word::

sage: w = words.BaumSweetWord(); w

word: 1101100101001001100100000100100101001001...

Block Definition::

sage: w = words.BaumSweetWord()

sage: f = lambda n: '1' if all(len(x)%2==0 for x in bin(n)[2:].split('1')) else '0'

sage: all(f(i) == w[i] for i in range(1,100))

True

"""

outer = WordMorphism('a->00,b->01,c->10,d->11')

inner = WordMorphism('a->aa,b->cb,c->ba,d->db')

return outer(inner.fixed_point('d'))

words = WordGenerator()

Coverage for local/lib/python2.7/site-packages/sage/combinat/words/word_generators.py : 82%

374 statements 305 run 69 missing 0 excluded