This module gathers functions that works for both finite and infinite words.
AUTHORS:
EXAMPLES:
sage: a = 0.618
sage: g = words.CodingOfRotationWord(alpha=a, beta=1-a, x=a)
sage: f = words.FibonacciWord()
sage: p = f.longest_common_prefix(g, length='finite')
sage: p
word: 0100101001001010010100100101001001010010...
sage: p.length()
231
Bases: sage.structure.sage_object.SageObject
EXAMPLES:
sage: w = Word('abaccefa')
sage: w. alphabet()
doctest:1: DeprecationWarning: alphabet() is deprecated, use parent().alphabet() instead
Python objects
sage: y = Words('456')('64654564')
sage: y.alphabet()
Ordered Alphabet ['4', '5', '6']
Returns the word obtained by applying the morphism to self.
INPUT:
EXAMPLES:
sage: w = Word("ab")
sage: d = {'a':'ab', 'b':'ba'}
sage: w.apply_morphism(d)
word: abba
sage: w.apply_morphism(WordMorphism(d))
word: abba
sage: w = Word('ababa')
sage: d = dict(a='ab', b='ba')
sage: d
{'a': 'ab', 'b': 'ba'}
sage: w.apply_morphism(d)
word: abbaabbaab
For infinite words:
sage: t = words.ThueMorseWord([0,1]); t
word: 0110100110010110100101100110100110010110...
sage: t.apply_morphism({0:8,1:9})
word: 8998988998898998988989988998988998898998...
Returns the image of self under the delta morphism. This is the word composed of the length of consecutive runs of the same letter in a given word.
OUTPUT:
Word over integers
EXAMPLES:
For finite words:
sage: W = Words('0123456789')
sage: W('22112122').delta()
word: 22112
sage: W('555008').delta()
word: 321
sage: W().delta()
word:
sage: Word('aabbabaa').delta()
word: 22112
For infinite words:
sage: t = words.ThueMorseWord()
sage: t.delta()
word: 1211222112112112221122211222112112112221...
Returns the word obtained by the diffences of consecutive letters of self.
INPUT:
self - A word over the integers.
EXAMPLES:
sage: w = Word([x^2 for x in range(10)])
sage: w.finite_differences()
word: 1,3,5,7,9,11,13,15,17
sage: w.finite_differences(mod=4)
word: 131313131
sage: w.finite_differences(mod=0)
word: 1,3,5,7,9,11,13,15,17
TESTS:
sage: w = Word([2,3,6])
sage: w.finite_differences()
word: 13
sage: w = Word([2,6])
sage: w.finite_differences()
word: 4
sage: w = Word([2])
sage: w.finite_differences()
word:
sage: w = Word()
sage: w.finite_differences()
word:
If the word is infinite, so is the result:
sage: w = Word(lambda n:n)
sage: u = w.finite_differences()
sage: u
word: 1111111111111111111111111111111111111111...
sage: type(u)
<class 'sage.combinat.words.word.InfiniteWord_iter_with_caching'>
Returns True if the length of self is zero, and False otherwise.
EXAMPLES:
sage: it = iter([])
sage: Word(it).is_empty()
True
sage: it = iter([1,2,3])
sage: Word(it).is_empty()
False
sage: from itertools import count
sage: Word(count()).is_empty()
False
Returns the iterated (-)palindromic closure of self.
INPUT:
OUTPUT:
word – the iterated (-)palindromic closure of self
EXAMPLES:
sage: w = Word('abc')
sage: w.iterated_right_palindromic_closure()
word: abacaba
sage: w = Word('aaa')
sage: w.iterated_right_palindromic_closure()
word: aaa
sage: w = Word('abbab')
sage: w.iterated_right_palindromic_closure()
word: ababaabababaababa
A right -palindromic closure:
sage: f = WordMorphism('a->b,b->a')
sage: w = Word('abbab')
sage: w.iterated_right_palindromic_closure(f=f)
word: abbaabbaababbaabbaabbaababbaabbaab
An infinite word:
sage: t = words.ThueMorseWord('ab')
sage: t.iterated_right_palindromic_closure()
word: ababaabababaababaabababaababaabababaabab...
There are two implementations computing the iterated right -palindromic closure, the latter being much more efficient:
sage: w = Word('abaab')
sage: u = w.iterated_right_palindromic_closure(algorithm='definition')
sage: v = w.iterated_right_palindromic_closure(algorithm='recursive')
sage: u
word: abaabaababaabaaba
sage: u == v
True
sage: w = words.RandomWord(8)
sage: u = w.iterated_right_palindromic_closure(algorithm='definition')
sage: v = w.iterated_right_palindromic_closure(algorithm='recursive')
sage: u == v
True
TESTS:
The empty word:
sage: w = Word()
sage: w.iterated_right_palindromic_closure()
word:
If the word is finite, so is the result:
sage: w = Word([0,1]*7)
sage: c = w.iterated_right_palindromic_closure()
sage: type(c)
<class 'sage.combinat.words.word.FiniteWord_iter_with_caching'>
REFERENCES:
Returns the length of self.
TESTS:
sage: from sage.combinat.words.word import Word_class
sage: w = Word(iter('abba'*100), length="unknown")
sage: w.length() is None
True
sage: w = Word(iter('abba'), length="finite")
sage: w.length()
4
sage: w = Word(iter([0,1,1,0,1,0,0,1]*100), length="unknown")
sage: w.length() is None
True
sage: w = Word(iter([0,1,1,0,1,0,0,1]), length="finite")
sage: w.length()
8
Returns True if self is lexicographically greater than other.
EXAMPLES:
sage: w = Word([1,2,3])
sage: u = Word([1,3,2])
sage: v = Word([3,2,1])
sage: w.lex_greater(u)
False
sage: v.lex_greater(w)
True
sage: a = Word("abba")
sage: b = Word("abbb")
sage: a.lex_greater(b)
False
sage: b.lex_greater(a)
True
For infinite words:
sage: t = words.ThueMorseWord()
sage: t[:10].lex_greater(t)
False
sage: t.lex_greater(t[:10])
True
Returns True if self is lexicographically less than other.
EXAMPLES:
sage: w = Word([1,2,3])
sage: u = Word([1,3,2])
sage: v = Word([3,2,1])
sage: w.lex_less(u)
True
sage: v.lex_less(w)
False
sage: a = Word("abba")
sage: b = Word("abbb")
sage: a.lex_less(b)
True
sage: b.lex_less(a)
False
For infinite words:
sage: t = words.ThueMorseWord()
sage: t.lex_less(t[:10])
False
sage: t[:10].lex_less(t)
True
Returns the longest common prefix of self and other.
INPUT:
OUTPUT:
word
EXAMPLES:
sage: f = lambda n : add(Integer(n).digits(2)) % 2
sage: t = Word(f)
sage: u = t[:10]
sage: t.longest_common_prefix(u)
word: 0110100110
The longest common prefix of two equal infinite words:
sage: t1 = Word(f)
sage: t2 = Word(f)
sage: t1.longest_common_prefix(t2)
word: 0110100110010110100101100110100110010110...
Useful to study the approximation of an infinite word:
sage: a = 0.618
sage: g = words.CodingOfRotationWord(alpha=a, beta=1-a, x=a)
sage: f = words.FibonacciWord()
sage: p = f.longest_common_prefix(g, length='finite')
sage: p.length()
231
TESTS:
sage: w = Word('12345')
sage: y = Word('1236777')
sage: w.longest_common_prefix(y)
word: 123
sage: w.longest_common_prefix(w)
word: 12345
sage: y.longest_common_prefix(w)
word: 123
sage: y.longest_common_prefix(y)
word: 1236777
sage: Word().longest_common_prefix(w)
word:
sage: w.longest_common_prefix(Word())
word:
sage: w.longest_common_prefix(w[:3])
word: 123
sage: Word("11").longest_common_prefix(Word("1"))
word: 1
sage: Word("1").longest_common_prefix(Word("11"))
word: 1
With infinite words:
sage: t = words.ThueMorseWord('ab')
sage: u = t[:10]
sage: u.longest_common_prefix(t)
word: abbabaabba
sage: u.longest_common_prefix(u)
word: abbabaabba
Returns the longest prefix of self having the given period.
INPUT:
OUTPUT:
word
EXAMPLES:
sage: Word([]).longest_periodic_prefix()
word:
sage: Word([1]).longest_periodic_prefix()
word: 1
sage: Word([1,2]).longest_periodic_prefix()
word: 1
sage: Word([1,1,2]).longest_periodic_prefix()
word: 11
sage: Word([1,2,1,2,1,3]).longest_periodic_prefix(2)
word: 12121
sage: type(_)
<class 'sage.combinat.words.word.FiniteWord_iter_with_caching'>
sage: Word(lambda n:0).longest_periodic_prefix()
word: 0000000000000000000000000000000000000000...
Returns an iterator over the palindrome prefixes of self.
INPUT:
OUTPUT:
iterator
EXAMPLES:
sage: w = Word('abaaba')
sage: for pp in w.palindrome_prefixes_iterator(): print pp
word:
word: a
word: aba
word: abaaba
sage: for pp in w.palindrome_prefixes_iterator(max_length=4): print pp
word:
word: a
word: aba
You can iterate over the palindrome prefixes of an infinite word:
sage: f = words.FibonacciWord()
sage: for pp in f.palindrome_prefixes_iterator(max_length=20): print pp
word:
word: 0
word: 010
word: 010010
word: 01001010010
word: 0100101001001010010
Returns the parent of self.
TESTS:
sage: Word(iter([1,2,3]), length="unknown").parent()
Words
sage: Word(range(12)).parent()
Words
sage: Word(range(4), alphabet=range(6)).parent()
Words over Ordered Alphabet [0, 1, 2, 3, 4, 5]
sage: Word(iter('abac'), alphabet='abc').parent()
Words over Ordered Alphabet ['a', 'b', 'c']
Returns the word defined by the partial sums of its prefixes.
INPUT:
self - A word over the integers.
start - integer, the first letter of the resulting word.
EXAMPLES:
sage: w = Word(range(10))
sage: w.partial_sums(0)
word: 0,0,1,3,6,10,15,21,28,36,45
sage: w.partial_sums(1)
word: 1,1,2,4,7,11,16,22,29,37,46
sage: w = Word([1,2,3,1,2,3,2,2,2,2])
sage: w.partial_sums(0, mod=None)
word: 0,1,3,6,7,9,12,14,16,18,20
sage: w.partial_sums(0, mod=0)
word: 0,1,3,6,7,9,12,14,16,18,20
sage: w.partial_sums(0, mod=8)
word: 01367146024
sage: w.partial_sums(0, mod=4)
word: 01323102020
sage: w.partial_sums(0, mod=2)
word: 01101100000
sage: w.partial_sums(0, mod=1)
word: 00000000000
TESTS:
If the word is infinite, so is the result:
sage: w = Word(lambda n:1)
sage: u = w.partial_sums(0)
sage: type(u)
<class 'sage.combinat.words.word.InfiniteWord_iter_with_caching'>
Returns an iterator over the prefixes of self.
INPUT:
OUTPUT:
iterator
EXAMPLES:
sage: w = Word('abaaba')
sage: for p in w.prefixes_iterator(): print p
word:
word: a
word: ab
word: aba
word: abaa
word: abaab
word: abaaba
sage: for p in w.prefixes_iterator(max_length=3): print p
word:
word: a
word: ab
word: aba
You can iterate over the prefixes of an infinite word:
sage: f = words.FibonacciWord()
sage: for p in f.prefixes_iterator(max_length=8): print p
word:
word: 0
word: 01
word: 010
word: 0100
word: 01001
word: 010010
word: 0100101
word: 01001010
TESTS:
sage: list(f.prefixes_iterator(max_length=0))
[word: ]
Returns the raw sequence of letters as a string.
EXAMPLES:
sage: Word('abbabaab').string_rep()
'abbabaab'
sage: Word([0, 1, 0, 0, 1]).string_rep()
'01001'
sage: Word([0,1,10,101]).string_rep()
'0,1,10,101'
sage: WordOptions(letter_separator='-')
sage: Word([0,1,10,101]).string_rep()
'0-1-10-101'
sage: WordOptions(letter_separator=',')
Returns a word over the integers whose letters are those output by self._to_integer_iterator()
EXAMPLES:
sage: from itertools import count
sage: w = Word(count()); w
word: 0,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,...
sage: w.to_integer_word()
word: 0,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,...
sage: w = Word(iter("abbacabba"), length="finite"); w
word: abbacabba
sage: w.to_integer_word()
word: 011020110
sage: w = Word(iter("abbacabba"), length="unknown"); w
word: abbacabba
sage: w.to_integer_word()
word: 011020110