Finite word#
AUTHORS:
Arnaud Bergeron
Amy Glen
Sébastien Labbé
Franco Saliola
Julien Leroy (March 2010): reduced_rauzy_graph
EXAMPLES:
Creation of a finite word#
Finite words from Python strings, lists and tuples:
sage: Word("abbabaab")
word: abbabaab
sage: Word([0, 1, 1, 0, 1, 0, 0, 1])
word: 01101001
sage: Word( ('a', 0, 5, 7, 'b', 9, 8) )
word: a057b98
Finite words from functions:
sage: f = lambda n : n%3
sage: Word(f, length=13)
word: 0120120120120
Finite words from iterators:
sage: from itertools import count
sage: Word(count(), length=10)
word: 0123456789
sage: Word( iter('abbccdef') )
word: abbccdef
Finite words from words via concatenation:
sage: u = Word("abcccabba")
sage: v = Word([0, 4, 8, 8, 3])
sage: u * v
word: abcccabba04883
sage: v * u
word: 04883abcccabba
sage: u + v
word: abcccabba04883
sage: u^3 * v^(8/5)
word: abcccabbaabcccabbaabcccabba04883048
Finite words from infinite words:
sage: vv = v^Infinity
sage: vv[10000:10015]
word: 048830488304883
Finite words in a specific combinatorial class:
sage: W = Words("ab")
sage: W
Finite and infinite words over {'a', 'b'}
sage: W("abbabaab")
word: abbabaab
sage: W(["a","b","b","a","b","a","a","b"])
word: abbabaab
sage: W( iter('ababab') )
word: ababab
Finite word as the image under a morphism:
sage: m = WordMorphism({0:[4,4,5,0],5:[0,5,5],4:[4,0,0,0]})
sage: m(0)
word: 4450
sage: m(0, order=2)
word: 400040000554450
sage: m(0, order=3)
word: 4000445044504450400044504450445044500550...
Note
The following two finite words have the same string representation:
sage: w = Word('010120')
sage: z = Word([0, 1, 0, 1, 2, 0])
sage: w
word: 010120
sage: z
word: 010120
but are not equal:
sage: w == z
False
Indeed, w and z are defined on different alphabets:
sage: w[2]
'0'
sage: z[2]
0
Functions and algorithms#
There are more than 100 functions defined on a finite word. Here are some of them:
sage: w = Word('abaabbba'); w
word: abaabbba
sage: w.is_palindrome()
False
sage: w.is_lyndon()
False
sage: w.number_of_factors()
28
sage: w.critical_exponent()
3
sage: print(w.lyndon_factorization())
(ab, aabbb, a)
sage: print(w.crochemore_factorization())
(a, b, a, ab, bb, a)
sage: st = w.suffix_tree()
sage: st
Implicit Suffix Tree of the word: abaabbba
sage: st.show(word_labels=True) # optional - sage.plot
sage: T = words.FibonacciWord('ab')
sage: T.longest_common_prefix(Word('abaabababbbbbb'))
word: abaababa
As matrix and many other sage objects, words have a parent:
sage: u = Word('xyxxyxyyy')
sage: u.parent()
Finite words over Set of Python objects of class 'object'
sage: v = Word('xyxxyxyyy', alphabet='xy')
sage: v.parent()
Finite words over {'x', 'y'}
Factors and Rauzy Graphs#
Enumeration of factors, the successive values returned by next(it)
can appear in a different order depending on hardware. Therefore we
mark the three first results of the test random
. The important test
is that the iteration stops properly on the fourth call:
sage: w = Word([4,5,6])^7
sage: it = w.factor_iterator(4)
sage: next(it) # random
word: 6456
sage: next(it) # random
word: 5645
sage: next(it) # random
word: 4564
sage: next(it)
Traceback (most recent call last):
...
StopIteration
The set of factors:
sage: sorted(w.factor_set(3))
[word: 456, word: 564, word: 645]
sage: sorted(w.factor_set(4))
[word: 4564, word: 5645, word: 6456]
sage: w.factor_set().cardinality()
61
Rauzy graphs:
sage: f = words.FibonacciWord()[:30]
sage: f.rauzy_graph(4) # optional - sage.graphs
Looped digraph on 5 vertices
sage: f.reduced_rauzy_graph(4) # optional - sage.graphs
Looped multi-digraph on 2 vertices
Left-special and bispecial factors:
sage: f.number_of_left_special_factors(7)
1
sage: f.bispecial_factors()
[word: , word: 0, word: 010, word: 010010, word: 01001010010]
- class sage.combinat.words.finite_word.CallableFromListOfWords(words)#
Bases:
tuple
A class to create a callable from a list of words. The concatenation of a list of words is obtained by creating a word from this callable.
- class sage.combinat.words.finite_word.Factorization(iterable=(), /)#
Bases:
list
A list subclass having a nicer representation for factorization of words.
- class sage.combinat.words.finite_word.FiniteWord_class#
Bases:
Word_class
- BWT()#
Return the Burrows-Wheeler Transform (BWT) of
self
.The Burrows-Wheeler transform of a finite word \(w\) is obtained from \(w\) by first listing the conjugates of \(w\) in lexicographic order and then concatenating the final letters of the conjugates in this order. See [BW1994].
EXAMPLES:
sage: Word('abaccaaba').BWT() word: cbaabaaca sage: Word('abaab').BWT() word: bbaaa sage: Word('bbabbaca').BWT() word: cbbbbaaa sage: Word('aabaab').BWT() word: bbaaaa sage: Word().BWT() word: sage: Word('a').BWT() word: a
- LZ_decomposition()#
Return the Crochemore factorization of
self
as an ordered list of factors.The Crochemore factorization or the Lempel-Ziv decomposition of a finite word \(w\) is the unique factorization: \((x_1, x_2, \ldots, x_n)\) of \(w\) with each \(x_i\) satisfying either: C1. \(x_i\) is a letter that does not appear in \(u = x_1\ldots x_{i-1}\); C2. \(x_i\) is the longest prefix of \(v = x_i\ldots x_n\) that also has an occurrence beginning within \(u = x_1\ldots x_{i-1}\). See [Cro1983].
EXAMPLES:
sage: x = Word('abababb') sage: x.crochemore_factorization() (a, b, abab, b) sage: mul(x.crochemore_factorization()) == x True sage: y = Word('abaababacabba') sage: y.crochemore_factorization() (a, b, a, aba, ba, c, ab, ba) sage: mul(y.crochemore_factorization()) == y True sage: x = Word([0,1,0,1,0,1,1]) sage: x.crochemore_factorization() (0, 1, 0101, 1) sage: mul(x.crochemore_factorization()) == x True
- abelian_complexity(n)#
Return the number of abelian vectors of factors of length
n
ofself
.EXAMPLES:
sage: w = words.FibonacciWord()[:100] sage: [w.abelian_complexity(i) for i in range(20)] [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
sage: w = words.ThueMorseWord()[:100] sage: [w.abelian_complexity(i) for i in range(20)] [1, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2]
- abelian_vector()#
Return the abelian vector of
self
counting the occurrences of each letter.The vector is defined w.r.t. the order of the alphabet of the parent. See also
evaluation_dict()
.INPUT:
self
– word having a parent on a finite alphabet
OUTPUT:
a list
EXAMPLES:
sage: W = Words('ab') sage: W('aaabbbbb').abelian_vector() [3, 5] sage: W('a').abelian_vector() [1, 0] sage: W().abelian_vector() [0, 0]
The result depends on the alphabet of the parent:
sage: W = Words('abc') sage: W('aabaa').abelian_vector() [4, 1, 0]
- abelian_vectors(n)#
Return the abelian vectors of factors of length
n
ofself
.The vectors are defined w.r.t. the order of the alphabet of the parent.
OUTPUT:
a set of tuples
EXAMPLES:
sage: W = Words([0,1,2]) sage: w = W([0,1,1,0,1,2,0,2,0,2]) sage: w.abelian_vectors(3) {(1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1)} sage: w[:5].abelian_vectors(3) {(1, 2, 0)} sage: w[5:].abelian_vectors(3) {(1, 0, 2), (2, 0, 1)}
sage: w = words.FibonacciWord()[:100] sage: sorted(w.abelian_vectors(0)) [(0, 0)] sage: sorted(w.abelian_vectors(1)) [(0, 1), (1, 0)] sage: sorted(w.abelian_vectors(7)) [(4, 3), (5, 2)]
The word must be defined with a parent on a finite alphabet:
sage: from itertools import count sage: w = Word(count(), alphabet=NN) sage: w[:2].abelian_vectors(2) Traceback (most recent call last): ... TypeError: The alphabet of the parent is infinite; define the word with a parent on a finite alphabet
- apply_permutation_to_letters(permutation)#
Return the word obtained by applying the permutation
permutation
of the alphabet ofself
to each letter ofself
.EXAMPLES:
sage: w = Words('abcd')('abcd') sage: p = [2,1,4,3] sage: w.apply_permutation_to_letters(p) word: badc sage: u = Words('dabc')('abcd') sage: u.apply_permutation_to_letters(p) word: dcba sage: w.apply_permutation_to_letters(Permutation(p)) word: badc sage: w.apply_permutation_to_letters(PermutationGroupElement(p)) word: badc
- apply_permutation_to_positions(permutation)#
Return the word obtained by permuting the positions of the letters in
self
according to the permutationpermutation
.EXAMPLES:
sage: w = Words('abcd')('abcd') sage: w.apply_permutation_to_positions([2,1,4,3]) word: badc sage: u = Words('dabc')('abcd') sage: u.apply_permutation_to_positions([2,1,4,3]) word: badc sage: w.apply_permutation_to_positions(Permutation([2,1,4,3])) word: badc sage: w.apply_permutation_to_positions(PermutationGroupElement([2,1,4,3])) word: badc sage: Word([1,2,3,4]).apply_permutation_to_positions([3,4,2,1]) word: 3421
- balance()#
Return the balance of
self
.The balance of a word is the smallest number \(q\) such that
self
is \(q\)-balanced [FV2002].A finite or infinite word \(w\) is said to be \(q\)-balanced if for any two factors \(u\), \(v\) of \(w\) of the same length, the difference between the number of \(x\)’s in each of \(u\) and \(v\) is at most \(q\) for all letters \(x\) in the alphabet of \(w\). A \(1\)-balanced word is simply said to be balanced. See Chapter 2 of [Lot2002].
OUTPUT:
integer
EXAMPLES:
sage: Word('1111111').balance() 0 sage: Word('001010101011').balance() 2 sage: Word('0101010101').balance() 1
sage: w = Word('11112222') sage: w.is_balanced(2) False sage: w.is_balanced(3) False sage: w.is_balanced(4) True sage: w.is_balanced(5) True sage: w.balance() 4
- bispecial_factors(n=None)#
Return the bispecial factors (of length
n
).A factor \(u\) of a word \(w\) is bispecial if it is right special and left special.
INPUT:
n
– integer (optional, default:None
). IfNone
, it returns all bispecial factors.
OUTPUT:
a list of words
EXAMPLES:
sage: w = words.FibonacciWord()[:30] sage: w.bispecial_factors() [word: , word: 0, word: 010, word: 010010, word: 01001010010]
sage: w = words.ThueMorseWord()[:30] sage: for i in range(10): ....: print("{} {}".format(i, sorted(w.bispecial_factors(i)))) 0 [word: ] 1 [word: 0, word: 1] 2 [word: 01, word: 10] 3 [word: 010, word: 101] 4 [word: 0110, word: 1001] 5 [] 6 [word: 011001, word: 100110] 7 [] 8 [word: 10010110] 9 []
- bispecial_factors_iterator(n=None)#
Return an iterator over the bispecial factors (of length
n
).A factor \(u\) of a word \(w\) is bispecial if it is right special and left special.
INPUT:
n
– integer (optional, default:None
). IfNone
, it returns an iterator over all bispecial factors.
EXAMPLES:
sage: w = words.ThueMorseWord()[:30] sage: for i in range(10): ....: for u in sorted(w.bispecial_factors_iterator(i)): ....: print("{} {}".format(i,u)) 0 1 0 1 1 2 01 2 10 3 010 3 101 4 0110 4 1001 6 011001 6 100110 8 10010110
sage: key = lambda u : (len(u), u) sage: for u in sorted(w.bispecial_factors_iterator(), key=key): u word: word: 0 word: 1 word: 01 word: 10 word: 010 word: 101 word: 0110 word: 1001 word: 011001 word: 100110 word: 10010110
- border()#
Return the longest word that is both a proper prefix and a proper suffix of
self
.EXAMPLES:
sage: Word('121212').border() word: 1212 sage: Word('12321').border() word: 1 sage: Word().border() is None True
- charge(check=True)#
Return the charge of
self
. This is defined as follows.If \(w\) is a permutation of length \(n\), (in other words, the evaluation of \(w\) is \((1, 1, \dots, 1)\)), the statistic charge(\(w\)) is given by \(\sum_{i=1}^n c_i(w)\) where \(c_1(w) = 0\) and \(c_i(w)\) is defined recursively by setting \(p_i\) equal to \(1\) if \(i\) appears to the right of \(i-1\) in \(w\) and \(0\) otherwise. Then we set \(c_i(w) = c_{i-1}(w) + p_i\).
EXAMPLES:
sage: Word([1, 2, 3]).charge() 3 sage: Word([3, 5, 1, 4, 2]).charge() == 0 + 1 + 1 + 2 + 2 True
If \(w\) is not a permutation, but the evaluation of \(w\) is a partition, the charge of \(w\) is defined to be the sum of its charge subwords (each of which will be a permutation). The first charge subword is found by starting at the end of \(w\) and moving left until the first \(1\) is found. This is marked, and we continue to move to the left until the first \(2\) is found, wrapping around from the beginning of the word back to the end, if necessary. We mark this \(2\), and continue on until we have marked the largest letter in \(w\). The marked letters, with relative order preserved, form the first charge subword of \(w\). This subword is removed, and the next charge subword is found in the same manner from the remaining letters. In the following example, \(w1, w2, w3\) are the charge subwords of \(w\).
EXAMPLES:
sage: w = Word([5,2,3,4,4,1,1,1,2,2,3]) sage: w1 = Word([5, 2, 4, 1, 3]) sage: w2 = Word([3, 4, 1, 2]) sage: w3 = Word([1, 2]) sage: w.charge() == w1.charge() + w2.charge() + w3.charge() True
Finally, if \(w\) does not have partition content, we apply the Lascoux-Schützenberger standardization operators \(s_i\) in such a manner as to obtain a word with partition content. (The word we obtain is independent of the choice of operators.) The charge is then defined to be the charge of this word:
sage: Word([3,3,2,1,1]).charge() 0 sage: Word([1,2,3,1,2]).charge() 2
Note that this differs from the definition of charge given in Macdonald’s book. The difference amounts to a choice of reading a word from left-to-right or right-to-left. The choice in Sage was made to agree with the definition of a reading word of a tableau in Sage, and seems to be the more common convention in the literature.
- cocharge()#
Return the cocharge of
self
. For a word \(w\), this can be defined as \(n_{ev} - ch(w)\), where \(ch(w)\) is the charge of \(w\) and \(ev\) is the evaluation of \(w\), and \(n_{ev}\) is \(\sum_{i<j} min(ev_i, ev_j)\).EXAMPLES:
sage: Word([1,2,3]).cocharge() 0 sage: Word([3,2,1]).cocharge() 3 sage: Word([1,1,2]).cocharge() 0 sage: Word([2,1,2]).cocharge() 1
- coerce(other)#
Try to return a pair of words with a common parent; raise an exception if this is not possible.
This function begins by checking if both words have the same parent. If this is the case, then no work is done and both words are returned as-is.
Otherwise it will attempt to convert
other
to the domain ofself
. If that fails, it will attempt to convertself
to the domain ofother
. If both attempts fail, it raises aTypeError
to signal failure.EXAMPLES:
sage: W1 = Words('abc'); W2 = Words('ab') sage: w1 = W1('abc'); w2 = W2('abba'); w3 = W1('baab') sage: w1.parent() is w2.parent() False sage: a, b = w1.coerce(w2) sage: a.parent() is b.parent() True sage: w1.parent() is w2.parent() False
- colored_vector(x=0, y=0, width='default', height=1, cmap='hsv', thickness=1, label=None)#
Return a vector (Graphics object) illustrating
self
. Each letter is represented by a coloured rectangle.If the parent of
self
is a class of words over a finite alphabet, then each letter in the alphabet is assigned a unique colour, and this colour will be the same every time this method is called. This is especially useful when plotting and comparing words defined on the same alphabet.If the alphabet is infinite, then the letters appearing in the word are used as the alphabet.
INPUT:
x
– (default:0
) bottom left x-coordinate of the vectory
– (default:0
) bottom left y-coordinate of the vectorwidth
– (default:'default'
) width of the vector. By default, the width is the length ofself
.height
– (default:1
) height of the vectorthickness
– (default:1
) thickness of the contourcmap
– (default:'hsv'
) color map; for available color map names type:import matplotlib.cm; list(matplotlib.cm.datad)
label
– string (default:None
) a label to add on the colored vector
OUTPUT:
Graphics
EXAMPLES:
sage: Word(range(20)).colored_vector() # optional - sage.plot Graphics object consisting of 21 graphics primitives sage: Word(range(100)).colored_vector(0,0,10,1) # optional - sage.plot Graphics object consisting of 101 graphics primitives sage: Words(range(100))(range(10)).colored_vector() # optional - sage.plot Graphics object consisting of 11 graphics primitives sage: w = Word('abbabaab') sage: w.colored_vector() # optional - sage.plot Graphics object consisting of 9 graphics primitives sage: w.colored_vector(cmap='autumn') # optional - sage.plot Graphics object consisting of 9 graphics primitives sage: Word(range(20)).colored_vector(label='Rainbow') # optional - sage.plot Graphics object consisting of 23 graphics primitives
When two words are defined under the same parent, same letters are mapped to same colors:
sage: W = Words(range(20)) sage: w = W(range(20)) sage: y = W(range(10,20)) sage: y.colored_vector(y=1, x=10) + w.colored_vector() # optional - sage.plot Graphics object consisting of 32 graphics primitives
- commutes_with(other)#
Return
True
ifself
commutes withother
, andFalse
otherwise.EXAMPLES:
sage: Word('12').commutes_with(Word('12')) True sage: Word('12').commutes_with(Word('11')) False sage: Word().commutes_with(Word('21')) True
- complete_return_words(fact)#
Return the set of complete return words of
fact
inself
.This is the set of all factors starting by the given factor and ending just after the next occurrence of this factor. See for instance [JV2000].
INPUT:
fact
– a non-empty finite word
OUTPUT:
a Python set of finite words
EXAMPLES:
sage: s = Word('21331233213231').complete_return_words(Word('2')) sage: sorted(s) [word: 2132, word: 213312, word: 2332] sage: Word('').complete_return_words(Word('213')) set() sage: Word('121212').complete_return_words(Word('1212')) {word: 121212}
- concatenate(other)#
Return the concatenation of
self
andother
.INPUT:
other
– a word over the same alphabet asself
EXAMPLES:
Concatenation may be made using
+
or*
operations:sage: w = Word('abadafd') sage: y = Word([5,3,5,8,7]) sage: w * y word: abadafd53587 sage: w + y word: abadafd53587 sage: w.concatenate(y) word: abadafd53587
Both words must be defined over the same alphabet:
sage: z = Word('12223', alphabet = '123') sage: z + y Traceback (most recent call last): ... ValueError: 5 not in alphabet
Eventually, it should work:
sage: z = Word('12223', alphabet = '123') sage: z + y #todo: not implemented word: 1222353587
- conjugate(pos)#
Return the conjugate at
pos
ofself
.pos
can be any integer, the distance used is the modulo by the length ofself
.EXAMPLES:
sage: Word('12112').conjugate(1) word: 21121 sage: Word().conjugate(2) word: sage: Word('12112').conjugate(8) word: 12121 sage: Word('12112').conjugate(-1) word: 21211
- conjugate_position(other)#
Return the position where
self
is conjugate withother
. ReturnNone
if there is no such position.EXAMPLES:
sage: Word('12113').conjugate_position(Word('31211')) 1 sage: Word('12131').conjugate_position(Word('12113')) is None True sage: Word().conjugate_position(Word('123')) is None True
- conjugates()#
Return the list of unique conjugates of
self
.EXAMPLES:
sage: Word(range(6)).conjugates() [word: 012345, word: 123450, word: 234501, word: 345012, word: 450123, word: 501234] sage: Word('cbbca').conjugates() [word: cbbca, word: bbcac, word: bcacb, word: cacbb, word: acbbc]
The result contains each conjugate only once:
sage: Word('abcabc').conjugates() [word: abcabc, word: bcabca, word: cabcab]
- conjugates_iterator()#
Return an iterator over the conjugates of
self
.EXAMPLES:
sage: it = Word(range(4)).conjugates_iterator() sage: for w in it: w word: 0123 word: 1230 word: 2301 word: 3012
- content(n=None)#
Return content of
self
.INPUT:
n
– (optional) an integer specifying the maximal letter in the alphabet
OUTPUT:
a list where the \(i\)-th entry indicates the multiplicity of the \(i\)-th letter in the alphabet in
self
EXAMPLES:
sage: w = Word([1,2,4,3,2,2,2]) sage: w.content() [1, 4, 1, 1] sage: w = Word([3,1]) sage: w.content() [1, 1] sage: w.content(n=3) [1, 0, 1] sage: w = Word([2,4],alphabet=[1,2,3,4]) sage: w.content(n=3) [0, 1, 0] sage: w.content() [0, 1, 0, 1]
- count(letter)#
Return the number of occurrences of
letter
inself
.INPUT:
letter
- a letter
OUTPUT:
integer
EXAMPLES:
sage: w = Word('abbabaab') sage: w.number_of_letter_occurrences('a') 4 sage: w.number_of_letter_occurrences('ab') 0
This methods is equivalent to
list(w).count(letter)
andtuple(w).count(letter)
, thuscount
is an alias for the methodnumber_of_letter_occurrences
:sage: list(w).count('a') 4 sage: w.count('a') 4
But notice that if
s
andw
are strings,Word(s).count(w)
counts the number occurrences ofw
as a letter inWord(s)
which is not the same ass.count(w)
which counts the number of occurrences of the stringw
insides
:sage: s = 'abbabaab' sage: s.count('ab') 3 sage: Word(s).count('ab') 0
- critical_exponent()#
Return the critical exponent of
self
.The critical exponent of a word is the supremum of the order of all its (finite) factors. See [Dej1972].
Note
The implementation here uses the suffix tree to enumerate all the factors. It should be improved (especially when the critical exponent is larger than 2).
EXAMPLES:
sage: Word('aaba').critical_exponent() 2 sage: Word('aabaa').critical_exponent() 2 sage: Word('aabaaba').critical_exponent() 7/3 sage: Word('ab').critical_exponent() 1 sage: Word('aba').critical_exponent() 3/2 sage: words.ThueMorseWord()[:20].critical_exponent() 2
For the Fibonacci word, the critical exponent is known to be \((5+\sqrt(5))/2\). With a prefix of length 500, we obtain a lower bound:
sage: words.FibonacciWord()[:500].critical_exponent() 320/89
It is an error to compute the critical exponent of the empty word:
sage: Word('').critical_exponent() Traceback (most recent call last): ... ValueError: no critical exponent for empty word
- crochemore_factorization()#
Return the Crochemore factorization of
self
as an ordered list of factors.The Crochemore factorization or the Lempel-Ziv decomposition of a finite word \(w\) is the unique factorization: \((x_1, x_2, \ldots, x_n)\) of \(w\) with each \(x_i\) satisfying either: C1. \(x_i\) is a letter that does not appear in \(u = x_1\ldots x_{i-1}\); C2. \(x_i\) is the longest prefix of \(v = x_i\ldots x_n\) that also has an occurrence beginning within \(u = x_1\ldots x_{i-1}\). See [Cro1983].
EXAMPLES:
sage: x = Word('abababb') sage: x.crochemore_factorization() (a, b, abab, b) sage: mul(x.crochemore_factorization()) == x True sage: y = Word('abaababacabba') sage: y.crochemore_factorization() (a, b, a, aba, ba, c, ab, ba) sage: mul(y.crochemore_factorization()) == y True sage: x = Word([0,1,0,1,0,1,1]) sage: x.crochemore_factorization() (0, 1, 0101, 1) sage: mul(x.crochemore_factorization()) == x True
- defect(f=None)#
Return the defect of
self
.The defect of a finite word \(w\) is given by the difference between the maximum number of possible palindromic factors in a word of length \(|w|\) and the actual number of palindromic factors contained in \(w\). It is well known that the maximum number of palindromic factors in \(w\) is \(|w|+1\) (see [DJP2001]).
An optional involution on letters
f
can be given. In that case, the f-palindromic defect (or pseudopalindromic defect, or theta-palindromic defect) of \(w\) is returned. It is a generalization of defect to f-palindromes. More precisely, the defect is \(D(w)=|w|+1-g_f(w)-|PAL_f(w)|\), where \(PAL_f(w)\) denotes the set of f-palindromic factors of \(w\) (including the empty word) and \(g_f(w)\) is the number of pairs \(\{a, f(a)\}\) such that \(a\) is a letter, \(a\) is not equal to \(f(a)\), and \(a\) or \(f(a)\) occurs in \(w\). In the case of usual palindromes (i.e., forf
not given or equal to the identity), \(g_f(w) = 0\) for all \(w\). See [BHNR2004] for usual palindromes and [Star2011] for f-palindromes.INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
). The default value corresponds to usual palindromes, i.e.,f
equal to the identity.
OUTPUT:
an integer – If
f
isNone
, the palindromic defect ofself
; otherwise, thef
-palindromic defect ofself
.EXAMPLES:
sage: Word('ara').defect() 0 sage: Word('abcacba').defect() 1
It is known that Sturmian words (see [DJP2001]) have zero defect:
sage: words.FibonacciWord()[:100].defect() 0 sage: sa = WordMorphism('a->ab,b->b') sage: sb = WordMorphism('a->a,b->ba') sage: w = (sa*sb*sb*sa*sa*sa*sb).fixed_point('a') sage: w[:30].defect() # optional - sage.modules 0 sage: w[110:140].defect() # optional - sage.modules 0
It is even conjectured that the defect of an aperiodic word which is a fixed point of a primitive morphism is either \(0\) or infinite (see [BBGL2008]):
sage: w = words.ThueMorseWord() sage: w[:50].defect() # optional - sage.modules 12 sage: w[:100].defect() # optional - sage.modules 16 sage: w[:300].defect() # optional - sage.modules 52
For generalized defect with an involution different from the identity, there is always a letter which is not a palindrome! This is the reason for the modification of the definition:
sage: f = WordMorphism('a->b,b->a') sage: Word('a').defect(f) 0 sage: Word('ab').defect(f) 0 sage: Word('aa').defect(f) 1 sage: Word('abbabaabbaababba').defect(f) 3
sage: f = WordMorphism('a->b,b->a,c->c') sage: Word('cabc').defect(f) 0 sage: Word('abcaab').defect(f) 2
Other examples:
sage: Word('000000000000').defect() 0 sage: Word('011010011001').defect() 2 sage: Word('0101001010001').defect() 0 sage: Word().defect() 0 sage: Word('abbabaabbaababba').defect() 2
- deg_inv_lex_less(other, weights=None)#
Return
True
if the wordself
is degree inverse lexicographically less thanother
.EXAMPLES:
sage: Word([1,2,4]).deg_inv_lex_less(Word([1,3,2])) False sage: Word([3,2,1]).deg_inv_lex_less(Word([1,2,3])) True
- deg_lex_less(other, weights=None)#
Return
True
ifself
is degree lexicographically less thanother
, andFalse
otherwise. The weight of each letter in the ordered alphabet is given byweights
, which defaults to[1, 2, 3, ...]
.EXAMPLES:
sage: Word([1,2,3]).deg_lex_less(Word([1,3,2])) True sage: Word([3,2,1]).deg_lex_less(Word([1,2,3])) False sage: W = Words(range(5)) sage: W([1,2,4]).deg_lex_less(W([1,3,2])) False sage: Word("abba").deg_lex_less(Word("abbb"), dict(a=1,b=2)) True sage: Word("abba").deg_lex_less(Word("baba"), dict(a=1,b=2)) True sage: Word("abba").deg_lex_less(Word("aaba"), dict(a=1,b=2)) False sage: Word("abba").deg_lex_less(Word("aaba"), dict(a=1,b=0)) True
- deg_rev_lex_less(other, weights=None)#
Return
True
ifself
is degree reverse lexicographically less thanother
.EXAMPLES:
sage: Word([3,2,1]).deg_rev_lex_less(Word([1,2,3])) False sage: Word([1,2,4]).deg_rev_lex_less(Word([1,3,2])) False sage: Word([1,2,3]).deg_rev_lex_less(Word([1,2,4])) True
- degree(weights=None)#
Return the weighted degree of
self
, where the weighted degree of each letter in the ordered alphabet is given byweights
, which defaults to[1, 2, 3, ...]
.INPUT:
weights
– a list or a tuple, or a dictionary keyed by the letters occurring inself
.
EXAMPLES:
sage: Word([1,2,3]).degree() 6 sage: Word([3,2,1]).degree() 6 sage: Words("ab")("abba").degree() 6 sage: Words("ab")("abba").degree([0,2]) 4 sage: Words("ab")("abba").degree([-1,-1]) -4 sage: Words("ab")("aabba").degree([1,1]) 5 sage: Words([1,2,4])([1,2,4]).degree() 6 sage: Word([1,2,4]).degree() 7 sage: Word("aabba").degree({'a':1,'b':2}) 7 sage: Word([0,1,0]).degree({0:17,1:0}) 34
- delta()#
Return the image of
self
under the delta morphism.The delta morphism, also known as the run-length encoding, is the word composed of the length of consecutive runs of the same letter in a given word.
EXAMPLES:
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
- delta_derivate(W=None)#
Return the derivative under delta for
self
.EXAMPLES:
sage: W = Words('12') sage: W('12211').delta_derivate() word: 22 sage: W('1').delta_derivate(Words([1])) word: 1 sage: W('2112').delta_derivate() word: 2 sage: W('2211').delta_derivate() word: 22 sage: W('112').delta_derivate() word: 2 sage: W('11222').delta_derivate(Words([1, 2, 3])) word: 3
- delta_derivate_left(W=None)#
Return the derivative under delta for
self
.EXAMPLES:
sage: W = Words('12') sage: W('12211').delta_derivate_left() word: 22 sage: W('1').delta_derivate_left(Words([1])) word: 1 sage: W('2112').delta_derivate_left() word: 21 sage: W('2211').delta_derivate_left() word: 22 sage: W('112').delta_derivate_left() word: 21 sage: W('11222').delta_derivate_left(Words([1, 2, 3])) word: 3
- delta_derivate_right(W=None)#
Return the right derivative under delta for
self
.EXAMPLES:
sage: W = Words('12') sage: W('12211').delta_derivate_right() word: 122 sage: W('1').delta_derivate_right(Words([1])) word: 1 sage: W('2112').delta_derivate_right() word: 12 sage: W('2211').delta_derivate_right() word: 22 sage: W('112').delta_derivate_right() word: 2 sage: W('11222').delta_derivate_right(Words([1, 2, 3])) word: 23
- delta_inv(W=None, s=None)#
Lift
self
via the delta operator to obtain a word containing the letters in alphabet (default is[0, 1]
). The letters used in the construction start withs
(default isalphabet[0]
) and cycle through alphabet.INPUT:
alphabet
– an iterables
– an object in the iterable
EXAMPLES:
sage: W = Words([1, 2]) sage: W([2, 2, 1, 1]).delta_inv() word: 112212 sage: W([1, 1, 1, 1]).delta_inv(Words('123')) word: 1231 sage: W([2, 2, 1, 1, 2]).delta_inv(s=2) word: 22112122
- evaluation()#
Return the abelian vector of
self
counting the occurrences of each letter.The vector is defined w.r.t. the order of the alphabet of the parent. See also
evaluation_dict()
.INPUT:
self
– word having a parent on a finite alphabet
OUTPUT:
a list
EXAMPLES:
sage: W = Words('ab') sage: W('aaabbbbb').abelian_vector() [3, 5] sage: W('a').abelian_vector() [1, 0] sage: W().abelian_vector() [0, 0]
The result depends on the alphabet of the parent:
sage: W = Words('abc') sage: W('aabaa').abelian_vector() [4, 1, 0]
- evaluation_dict()#
Return a dictionary keyed by the letters occurring in
self
with values the number of occurrences of the letter.EXAMPLES:
sage: Word([2,1,4,2,3,4,2]).evaluation_dict() {1: 1, 2: 3, 3: 1, 4: 2} sage: Word('badbcdb').evaluation_dict() {'a': 1, 'b': 3, 'c': 1, 'd': 2} sage: Word().evaluation_dict() {}
sage: f = Word('1213121').evaluation_dict() # keys appear in random order {'1': 4, '2': 2, '3': 1}
- evaluation_partition()#
Return the evaluation of the word w as a partition.
EXAMPLES:
sage: Word("acdabda").evaluation_partition() [3, 2, 1, 1] sage: Word([2,1,4,2,3,4,2]).evaluation_partition() [3, 2, 1, 1]
- evaluation_sparse()#
Return a list representing the evaluation of
self
. The entries of the list are two-element lists[a, n]
, wherea
is a letter occurring inself
andn
is the number of occurrences ofa
inself
.EXAMPLES:
sage: sorted(Word([4,4,2,5,2,1,4,1]).evaluation_sparse()) [(1, 2), (2, 2), (4, 3), (5, 1)] sage: sorted(Word("abcaccab").evaluation_sparse()) [('a', 3), ('b', 2), ('c', 3)]
- exponent()#
Return the exponent of
self
.OUTPUT:
integer – the exponent
EXAMPLES:
sage: Word('1231').exponent() 1 sage: Word('121212').exponent() 3 sage: Word().exponent() 0
- factor_complexity(n)#
Return the number of distinct factors of length
n
ofself
.INPUT:
n
– the length of the factors.
EXAMPLES:
sage: w = words.FibonacciWord()[:100] sage: [w.factor_complexity(i) for i in range(20)] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
sage: w = words.ThueMorseWord()[:1000] sage: [w.factor_complexity(i) for i in range(20)] [1, 2, 4, 6, 10, 12, 16, 20, 22, 24, 28, 32, 36, 40, 42, 44, 46, 48, 52, 56]
- factor_iterator(n=None)#
Generate distinct factors of
self
.INPUT:
n
– an integer, orNone
.
OUTPUT:
If
n
is an integer, returns an iterator over all distinct factors of lengthn
. Ifn
isNone
, returns an iterator generating all distinct factors.EXAMPLES:
sage: w = Word('1213121') sage: sorted( w.factor_iterator(0) ) [word: ] sage: sorted( w.factor_iterator(10) ) [] sage: sorted( w.factor_iterator(1) ) [word: 1, word: 2, word: 3] sage: sorted( w.factor_iterator(4) ) [word: 1213, word: 1312, word: 2131, word: 3121] sage: sorted( w.factor_iterator() ) [word: , word: 1, word: 12, word: 121, word: 1213, word: 12131, word: 121312, word: 1213121, word: 13, word: 131, word: 1312, word: 13121, word: 2, word: 21, word: 213, word: 2131, word: 21312, word: 213121, word: 3, word: 31, word: 312, word: 3121]
sage: u = Word([1,2,1,2,3]) sage: sorted( u.factor_iterator(0) ) [word: ] sage: sorted( u.factor_iterator(10) ) [] sage: sorted( u.factor_iterator(1) ) [word: 1, word: 2, word: 3] sage: sorted( u.factor_iterator(5) ) [word: 12123] sage: sorted( u.factor_iterator() ) [word: , word: 1, word: 12, word: 121, word: 1212, word: 12123, word: 123, word: 2, word: 21, word: 212, word: 2123, word: 23, word: 3]
sage: xxx = Word("xxx") sage: sorted( xxx.factor_iterator(0) ) [word: ] sage: sorted( xxx.factor_iterator(4) ) [] sage: sorted( xxx.factor_iterator(2) ) [word: xx] sage: sorted( xxx.factor_iterator() ) [word: , word: x, word: xx, word: xxx]
sage: e = Word() sage: sorted( e.factor_iterator(0) ) [word: ] sage: sorted( e.factor_iterator(17) ) [] sage: sorted( e.factor_iterator() ) [word: ]
- factor_occurrences_in(other)#
Return an iterator over all occurrences (including overlapping ones) of
self
inother
in their order of appearance.Warning
This method is deprecated since 2020 and will be removed in a later version of SageMath. Use
factor_occurrences_iterator()
instead.EXAMPLES:
sage: u = Word('121') sage: w = Word('121213211213') sage: list(u.factor_occurrences_in(w)) doctest:warning ... DeprecationWarning: f.factor_occurrences_in(w) is deprecated. Use w.factor_occurrences_iterator(f) instead. See https://github.com/sagemath/sage/issues/30187 for details. [0, 2, 8]
- factor_set(n=None, algorithm='suffix tree')#
Return the set of factors (of length
n
) ofself
.INPUT:
n
– an integer orNone
(default:None
).algorithm
– string (default:'suffix tree'
), takes the following values:'suffix tree'
– construct and use the suffix tree of the word'naive'
– algorithm uses a sliding window
OUTPUT:
If
n
is an integer, returns the set of all distinct factors of lengthn
. Ifn
isNone
, returns the set of all distinct factors.EXAMPLES:
sage: w = Word('121') sage: sorted(w.factor_set()) [word: , word: 1, word: 12, word: 121, word: 2, word: 21] sage: sorted(w.factor_set(algorithm='naive')) [word: , word: 1, word: 12, word: 121, word: 2, word: 21]
sage: w = Word('1213121') sage: for i in range(w.length()): sorted(w.factor_set(i)) [word: ] [word: 1, word: 2, word: 3] [word: 12, word: 13, word: 21, word: 31] [word: 121, word: 131, word: 213, word: 312] [word: 1213, word: 1312, word: 2131, word: 3121] [word: 12131, word: 13121, word: 21312] [word: 121312, word: 213121]
sage: w = Word([1,2,1,2,3]) sage: s = w.factor_set() sage: sorted(s) [word: , word: 1, word: 12, word: 121, word: 1212, word: 12123, word: 123, word: 2, word: 21, word: 212, word: 2123, word: 23, word: 3]
- find(sub, start=0, end=None)#
Return the index of the first occurrence of
sub
inself
, such thatsub
is contained withinself[start:end]
. Return-1
on failure.INPUT:
sub
– string, list, tuple or word to search for.start
– non-negative integer (default:0
) specifying the position from which to start the search.end
– non-negative integer (default:None
) specifying the position at which the search must stop. IfNone
, then the search is performed up to the end of the string.
OUTPUT:
a non-negative integer or
-1
EXAMPLES:
sage: w = Word([0,1,0,0,1]) sage: w.find(Word([1,0])) 1
The
sub
argument can also be a tuple or a list:sage: w.find([1,0]) 1 sage: w.find((1,0)) 1
Examples using
start
andend
:sage: w.find(Word([0,1]), start=1) 3 sage: w.find(Word([0,1]), start=1, end=5) 3 sage: w.find(Word([0,1]), start=1, end=4) == -1 True sage: w.find(Word([1,1])) == -1 True sage: w.find("aa") -1
Instances of
Word_str
handle string inputs as well:sage: w = Word('abac') sage: w.find('a') 0 sage: w.find('ba') 1
- first_pos_in(other)#
Return the position of the first occurrence of
self
inother
, orNone
ifself
is not a factor ofother
.Warning
This method is deprecated since 2020 and will be removed in a later version of SageMath. Use
first_occurrence()
instead.EXAMPLES:
sage: Word('12').first_pos_in(Word('131231')) doctest:warning ... DeprecationWarning: f.first_pos_in(w) is deprecated. Use w.first_occurrence(f) instead. See https://github.com/sagemath/sage/issues/30187 for details. 2 sage: Word('32').first_pos_in(Word('131231')) is None True
- foata_bijection()#
Return word
self
under the Foata bijection.The Foata bijection \(\phi\) is a bijection on the set of words of given content (by a slight generalization of Section 2 in [FS1978]). It can be defined by induction on the size of the word: Given a word \(w_1 w_2 \cdots w_n\), start with \(\phi(w_1) = w_1\). At the \(i\)-th step, if \(\phi(w_1 w_2 \cdots w_i) = v_1 v_2 \cdots v_i\), we define \(\phi(w_1 w_2 \cdots w_i w_{i+1})\) by placing \(w_{i+1}\) on the end of the word \(v_1 v_2 \cdots v_i\) and breaking the word up into blocks as follows. If \(w_{i+1} \ge v_i\), place a vertical line to the right of each \(v_k\) for which \(w_{i+1} \ge v_k\). Otherwise, if \(w_{i+1} < v_i\), place a vertical line to the right of each \(v_k\) for which \(w_{i+1} < v_k\). In either case, place a vertical line at the start of the word as well. Now, within each block between vertical lines, cyclically shift the entries one place to the right.
For instance, to compute \(\phi([4,1,5,4,2,2,3])\), the sequence of words is
\(4\),
\(|4|1 \to 41\),
\(|4|1|5 \to 415\),
\(|415|4 \to 5414\),
\(|5|4|14|2 \to 54412\),
\(|5441|2|2 \to 154422\),
\(|1|5442|2|3 \to 1254423\).
So \(\phi([4,1,5,4,2,2,3]) = [1,2,5,4,4,2,3]\).
See also
EXAMPLES:
sage: w = Word([2,2,2,1,1,1]) sage: w.foata_bijection() word: 112221 sage: w = Word([2,2,1,2,2,2,1,1,2,1]) sage: w.foata_bijection() word: 2122212211 sage: w = Word([4,1,5,4,2,2,3]) sage: w.foata_bijection() word: 1254423
- good_suffix_table()#
Return a table of the maximum skip you can do in order not to miss a possible occurrence of
self
in a word.This is a part of the Boyer-Moore algorithm to find factors. See [BM1977].
EXAMPLES:
sage: Word('121321').good_suffix_table() [5, 5, 5, 5, 3, 3, 1] sage: Word('12412').good_suffix_table() [3, 3, 3, 3, 3, 1]
- has_period(p)#
Return
True
ifself
has the periodp
,False
otherwise.Note
By convention, integers greater than the length of
self
are periods ofself
.INPUT:
p
– an integer to check if it is a period ofself
.
EXAMPLES:
sage: w = Word('ababa') sage: w.has_period(2) True sage: w.has_period(3) False sage: w.has_period(4) True sage: w.has_period(-1) False sage: w.has_period(5) True sage: w.has_period(6) True
- has_prefix(other)#
Test whether
self
hasother
as a prefix.INPUT:
other
– a word, or data describing a word
OUTPUT:
boolean
EXAMPLES:
sage: w = Word("abbabaabababa") sage: u = Word("abbab") sage: w.has_prefix(u) True sage: u.has_prefix(w) False sage: u.has_prefix("abbab") True
sage: w = Word([0,1,1,0,1,0,0,1,0,1,0,1,0]) sage: u = Word([0,1,1,0,1]) sage: w.has_prefix(u) True sage: u.has_prefix(w) False sage: u.has_prefix([0,1,1,0,1]) True
- has_suffix(other)#
Test whether
self
hasother
as a suffix.Note
Some word datatype classes, like
WordDatatype_str
, override this method.INPUT:
other
– a word, or data describing a word
OUTPUT:
boolean
EXAMPLES:
sage: w = Word("abbabaabababa") sage: u = Word("ababa") sage: w.has_suffix(u) True sage: u.has_suffix(w) False sage: u.has_suffix("ababa") True
sage: w = Word([0,1,1,0,1,0,0,1,0,1,0,1,0]) sage: u = Word([0,1,0,1,0]) sage: w.has_suffix(u) True sage: u.has_suffix(w) False sage: u.has_suffix([0,1,0,1,0]) True
- implicit_suffix_tree()#
Return the implicit suffix tree of
self
.The suffix tree of a word \(w\) is a compactification of the suffix trie for \(w\). The compactification removes all nodes that have exactly one incoming edge and exactly one outgoing edge. It consists of two components: a tree and a word. Thus, instead of labelling the edges by factors of \(w\), we can label them by indices of the occurrence of the factors in \(w\).
Type
sage.combinat.words.suffix_trees.ImplicitSuffixTree?
for more information.EXAMPLES:
sage: w = Word("cacao") sage: w.implicit_suffix_tree() Implicit Suffix Tree of the word: cacao
sage: w = Word([0,1,0,1,1]) sage: w.implicit_suffix_tree() Implicit Suffix Tree of the word: 01011
- inv_lex_less(other)#
Return
True
ifself
is inverse lexicographically less thanother
.EXAMPLES:
sage: Word([1,2,4]).inv_lex_less(Word([1,3,2])) False sage: Word([3,2,1]).inv_lex_less(Word([1,2,3])) True
- inversions()#
Return a list of the inversions of
self
. An inversion is a pair \((i,j)\) of non-negative integers \(i < j\) such thatself[i] > self[j]
.EXAMPLES:
sage: Word([1,2,3,2,2,1]).inversions() [[1, 5], [2, 3], [2, 4], [2, 5], [3, 5], [4, 5]] sage: Words([3,2,1])([1,2,3,2,2,1]).inversions() [[0, 1], [0, 2], [0, 3], [0, 4], [1, 2]] sage: Word('abbaba').inversions() [[1, 3], [1, 5], [2, 3], [2, 5], [4, 5]] sage: Words('ba')('abbaba').inversions() [[0, 1], [0, 2], [0, 4], [3, 4]]
- is_balanced(q=1)#
Return
True
ifself
isq
-balanced, andFalse
otherwise.A finite or infinite word \(w\) is said to be \(q\)-balanced if for any two factors \(u\), \(v\) of \(w\) of the same length, the difference between the number of \(x\)’s in each of \(u\) and \(v\) is at most \(q\) for all letters \(x\) in the alphabet of \(w\). A \(1\)-balanced word is simply said to be balanced. See for instance [CFZ2000] and Chapter 2 of [Lot2002].
INPUT:
q
– integer (default:1
), the balance level
OUTPUT:
boolean – the result
EXAMPLES:
sage: Word('1213121').is_balanced() True sage: Word('1122').is_balanced() False sage: Word('121333121').is_balanced() False sage: Word('121333121').is_balanced(2) False sage: Word('121333121').is_balanced(3) True sage: Word('121122121').is_balanced() False sage: Word('121122121').is_balanced(2) True
- is_cadence(seq)#
Return
True
ifseq
is a cadence ofself
, andFalse
otherwise.A cadence is an increasing sequence of indexes that all map to the same letter.
EXAMPLES:
sage: Word('121132123').is_cadence([0, 2, 6]) True sage: Word('121132123').is_cadence([0, 1, 2]) False sage: Word('121132123').is_cadence([]) True
- is_christoffel()#
Return
True
ifself
is a Christoffel word, andFalse
otherwise.The Christoffel word of slope \(p/q\) is obtained from the Cayley graph of \(\ZZ/(p+q)\ZZ\) with generator \(q\) as follows. If \(u \rightarrow v\) is an edge in the Cayley graph, then, \(v = u + p \mod{p+q}\). Let \(a\),`b` be the alphabet of \(w\). Label the edge \(u \rightarrow v\) by \(a\) if \(u < v\) and \(b\) otherwise. The Christoffel word is the word obtained by reading the edge labels along the cycle beginning from \(0\).
Equivalently, \(w\) is a Christoffel word iff \(w\) is a symmetric non-empty word and \(w[1:n-1]\) is a palindrome.
See for instance [Ber2007] and [BLRS2009].
INPUT:
self
– word
OUTPUT:
boolean –
True
ifself
is a Christoffel word,False
otherwise.EXAMPLES:
sage: Word('00100101').is_christoffel() True sage: Word('aab').is_christoffel() True sage: Word().is_christoffel() False sage: Word('123123123').is_christoffel() False sage: Word('00100').is_christoffel() False sage: Word('0').is_christoffel() True
- is_conjugate_with(other)#
Return
True
ifself
is a conjugate ofother
, andFalse
otherwise.INPUT:
other
– a finite word
OUTPUT:
bool
EXAMPLES:
sage: w = Word([0..20]) sage: z = Word([7..20] + [0..6]) sage: w word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 sage: z word: 7,8,9,10,11,12,13,14,15,16,17,18,19,20,0,1,2,3,4,5,6 sage: w.is_conjugate_with(z) True sage: z.is_conjugate_with(w) True sage: u = Word([4]*21) sage: u.is_conjugate_with(w) False sage: u.is_conjugate_with(z) False
Both words must be finite:
sage: w = Word(iter([2]*100),length='unknown') sage: z = Word([2]*100) sage: z.is_conjugate_with(w) #TODO: Not implemented for word of unknown length True sage: wf = Word(iter([2]*100),length='finite') sage: z.is_conjugate_with(wf) True sage: wf.is_conjugate_with(z) True
- is_cube()#
Return
True
ifself
is a cube, andFalse
otherwise.EXAMPLES:
sage: Word('012012012').is_cube() True sage: Word('01010101').is_cube() False sage: Word().is_cube() True sage: Word('012012').is_cube() False
- is_cube_free()#
Return
True
ifself
does not contain cubes, andFalse
otherwise.EXAMPLES:
sage: Word('12312').is_cube_free() True sage: Word('32221').is_cube_free() False sage: Word().is_cube_free() True
- is_empty()#
Return
True
if the length ofself
is zero, andFalse
otherwise.EXAMPLES:
sage: Word([]).is_empty() True sage: Word('a').is_empty() False
- is_factor(other)#
Return
True
ifself
is a factor ofother
, andFalse
otherwise.A finite word \(u\in A^*\) is a factor of a finite word \(v\in A^*\) if there exists \(p,s\in A^*\) such that \(v=pus\).
EXAMPLES:
sage: u = Word('2113') sage: w = Word('123121332131233121132123') sage: u.is_factor(w) True sage: u = Word('321') sage: w = Word('1231241231312312312') sage: u.is_factor(w) False
The empty word is factor of another word:
sage: Word().is_factor(Word()) True sage: Word().is_factor(Word('a')) True sage: Word().is_factor(Word([1,2,3])) True sage: Word().is_factor(Word(lambda n:n, length=5)) True
- is_finite()#
Return
True
.EXAMPLES:
sage: Word([]).is_finite() True sage: Word('a').is_finite() True
- is_full(f=None)#
Return
True
ifself
has defect \(0\), andFalse
otherwise.A word is full (or rich) if its defect is zero (see [BHNR2004]).
If
f
is given, then thef
-palindromic defect is used (see [PeSt2011]).INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
).
OUTPUT:
boolean – If
f
isNone
, whetherself
is full; otherwise, whetherself
is full off
-palindromes.EXAMPLES:
sage: words.ThueMorseWord()[:100].is_full() False sage: words.FibonacciWord()[:100].is_full() True sage: Word('000000000000000').is_full() True sage: Word('011010011001').is_full() False sage: Word('2194').is_full() True sage: Word().is_full() True
sage: f = WordMorphism('a->b,b->a') sage: Word().is_full(f) True sage: w = Word('ab') sage: w.is_full() True sage: w.is_full(f) True
sage: f = WordMorphism('a->b,b->a') sage: Word('abab').is_full(f) True sage: Word('abba').is_full(f) False
A simple example of an infinite word full of f-palindromes:
sage: p = WordMorphism({0:'abc',1:'ab'}) sage: f = WordMorphism('a->b,b->a,c->c') sage: p(words.FibonacciWord()[:50]).is_full(f) True sage: p(words.FibonacciWord()[:150]).is_full(f) True
- is_lyndon()#
Return
True
ifself
is a Lyndon word, andFalse
otherwise.A Lyndon word is a non-empty word that is lexicographically smaller than each of its proper suffixes (for the given order on its alphabet). That is, \(w\) is a Lyndon word if \(w\) is non-empty and for each factorization \(w = uv\) (with \(u\), \(v\) both non-empty), we have \(w < v\).
Equivalently, \(w\) is a Lyndon word iff \(w\) is a non-empty word that is lexicographically smaller than each of its proper conjugates for the given order on its alphabet.
See for instance [Lot1983].
EXAMPLES:
sage: Word('123132133').is_lyndon() True sage: Word().is_lyndon() False sage: Word('122112').is_lyndon() False
- is_overlap()#
Return
True
ifself
is an overlap, andFalse
otherwise.EXAMPLES:
sage: Word('12121').is_overlap() True sage: Word('123').is_overlap() False sage: Word('1231').is_overlap() False sage: Word('123123').is_overlap() False sage: Word('1231231').is_overlap() True sage: Word().is_overlap() False
- is_palindrome(f=None)#
Return
True
ifself
is a palindrome (or af
-palindrome), andFalse
otherwise.Let \(f : \Sigma \rightarrow \Sigma\) be an involution that extends to a morphism on \(\Sigma^*\). We say that \(w\in\Sigma^*\) is a `f`-palindrome if \(w=f(\tilde{w})\) [Lab2008]. Also called `f`-pseudo-palindrome [AZZ2005].
INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
). The default value corresponds to usual palindromes, i.e.,f
equal to the identity.
EXAMPLES:
sage: Word('esope reste ici et se repose').is_palindrome() False sage: Word('esoperesteicietserepose').is_palindrome() True sage: Word('I saw I was I').is_palindrome() True sage: Word('abbcbba').is_palindrome() True sage: Word('abcbdba').is_palindrome() False
Some \(f\)-palindromes:
sage: f = WordMorphism('a->b,b->a') sage: Word('aababb').is_palindrome(f) True
sage: f = WordMorphism('a->b,b->a,c->c') sage: Word('abacbacbab').is_palindrome(f) True
sage: f = WordMorphism({'a':'b','b':'a'}) sage: Word('aababb').is_palindrome(f) True
sage: f = WordMorphism({0:[1],1:[0]}) sage: w = words.ThueMorseWord()[:8]; w word: 01101001 sage: w.is_palindrome(f) True
The word must be in the domain of the involution:
sage: f = WordMorphism('a->a') sage: Word('aababb').is_palindrome(f) Traceback (most recent call last): ... KeyError: 'b'
- is_prefix(other)#
Return
True
ifself
is a prefix ofother
, andFalse
otherwise.EXAMPLES:
sage: w = Word('0123456789') sage: y = Word('012345') sage: y.is_prefix(w) True sage: w.is_prefix(y) False sage: w.is_prefix(Word()) False sage: Word().is_prefix(w) True sage: Word().is_prefix(Word()) True
- is_primitive()#
Return
True
ifself
is primitive, andFalse
otherwise.A finite word \(w\) is primitive if it is not a positive integer power of a shorter word.
EXAMPLES:
sage: Word('1231').is_primitive() True sage: Word('111').is_primitive() False
- is_proper_prefix(other)#
Return
True
ifself
is a proper prefix ofother
, andFalse
otherwise.EXAMPLES:
sage: Word('12').is_proper_prefix(Word('123')) True sage: Word('12').is_proper_prefix(Word('12')) False sage: Word().is_proper_prefix(Word('123')) True sage: Word('123').is_proper_prefix(Word('12')) False sage: Word().is_proper_prefix(Word()) False
- is_proper_suffix(other)#
Return
True
ifself
is a proper suffix ofother
, andFalse
otherwise.EXAMPLES:
sage: Word('23').is_proper_suffix(Word('123')) True sage: Word('12').is_proper_suffix(Word('12')) False sage: Word().is_proper_suffix(Word('123')) True sage: Word('123').is_proper_suffix(Word('12')) False
- is_quasiperiodic()#
Return
True
ifself
is quasiperiodic, andFalse
otherwise.A finite or infinite word \(w\) is quasiperiodic if it can be constructed by concatenations and superpositions of one of its proper factors \(u\), which is called a quasiperiod of \(w\). See for instance [AE1993], [Mar2004], and [GLR2008].
EXAMPLES:
sage: Word('abaababaabaababaaba').is_quasiperiodic() True sage: Word('abacaba').is_quasiperiodic() False sage: Word('a').is_quasiperiodic() False sage: Word().is_quasiperiodic() False sage: Word('abaaba').is_quasiperiodic() True
- is_rich(f=None)#
Return
True
ifself
has defect \(0\), andFalse
otherwise.A word is full (or rich) if its defect is zero (see [BHNR2004]).
If
f
is given, then thef
-palindromic defect is used (see [PeSt2011]).INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
).
OUTPUT:
boolean – If
f
isNone
, whetherself
is full; otherwise, whetherself
is full off
-palindromes.EXAMPLES:
sage: words.ThueMorseWord()[:100].is_full() False sage: words.FibonacciWord()[:100].is_full() True sage: Word('000000000000000').is_full() True sage: Word('011010011001').is_full() False sage: Word('2194').is_full() True sage: Word().is_full() True
sage: f = WordMorphism('a->b,b->a') sage: Word().is_full(f) True sage: w = Word('ab') sage: w.is_full() True sage: w.is_full(f) True
sage: f = WordMorphism('a->b,b->a') sage: Word('abab').is_full(f) True sage: Word('abba').is_full(f) False
A simple example of an infinite word full of f-palindromes:
sage: p = WordMorphism({0:'abc',1:'ab'}) sage: f = WordMorphism('a->b,b->a,c->c') sage: p(words.FibonacciWord()[:50]).is_full(f) True sage: p(words.FibonacciWord()[:150]).is_full(f) True
- is_smooth_prefix()#
Return
True
ifself
is the prefix of a smooth word, andFalse
otherwise.Let \(A_k = \{1, \ldots ,k\}\), \(k \geq 2\). An infinite word \(w\) in \(A_k^\omega\) is said to be smooth if and only if for all positive integers \(m\), \(\Delta^m(w)\) is in \(A_k^\omega\), where \(\Delta(w)\) is the word obtained from \(w\) by composing the length of consecutive runs of the same letter in \(w\). See for instance [BL2003] and [BDLV2006].
INPUT:
self
– must be a word over the integers to get something other thanFalse
OUTPUT:
boolean – whether
self
is a smooth prefix or notEXAMPLES:
sage: W = Words([1, 2]) sage: W([1, 1, 2, 2, 1, 2, 1, 1]).is_smooth_prefix() True sage: W([1, 2, 1, 2, 1, 2]).is_smooth_prefix() False
- is_square()#
Return
True
ifself
is a square, andFalse
otherwise.EXAMPLES:
sage: Word([1,0,0,1]).is_square() False sage: Word('1212').is_square() True sage: Word('1213').is_square() False sage: Word('12123').is_square() False sage: Word().is_square() True
- is_square_free()#
Return
True
ifself
does not contain squares, andFalse
otherwise.EXAMPLES:
sage: Word('12312').is_square_free() True sage: Word('31212').is_square_free() False sage: Word().is_square_free() True
- is_sturmian_factor()#
Tell whether
self
is a factor of a Sturmian word.The finite word
self
must be defined on a two-letter alphabet.Equivalently, tells whether
self
is balanced. The advantage over theis_balanced
method is that this one runs in linear time whereasis_balanced
runs in quadratic time.OUTPUT:
boolean – the result
EXAMPLES:
sage: w = Word('0111011011011101101',alphabet='01') sage: w.is_sturmian_factor() True
sage: words.LowerMechanicalWord(random(),alphabet='01')[:100].is_sturmian_factor() True sage: words.CharacteristicSturmianWord(random())[:100].is_sturmian_factor() True
sage: w = Word('aabb',alphabet='ab') sage: w.is_sturmian_factor() False sage: s1 = WordMorphism('a->ab,b->b') sage: s2 = WordMorphism('a->ba,b->b') sage: s3 = WordMorphism('a->a,b->ba') sage: s4 = WordMorphism('a->a,b->ab') sage: W = Words('ab') sage: w = W('ab') sage: for i in range(8): w = choice([s1,s2,s3,s4])(w) sage: w.is_sturmian_factor() True
Famous words:
sage: words.FibonacciWord()[:100].is_sturmian_factor() True sage: words.ThueMorseWord()[:1000].is_sturmian_factor() False sage: words.KolakoskiWord()[:1000].is_sturmian_factor() False
See [Arn2002], [Ser1985], and [SU2009].
AUTHOR:
Thierry Monteil
- is_subword_of(other)#
Return
True
ifself
is a subword ofother
, andFalse
otherwise.A finite word \(u\) is a subword of a finite word \(v\) if \(u\) is a subsequence of \(v\). See Chapter 6 on Subwords in [Lot1997].
Some references define subword as a consecutive subsequence. Use
is_factor()
if this is what you need.INPUT:
other
– a finite wordEXAMPLES:
sage: Word('bb').is_subword_of(Word('ababa')) True sage: Word('bbb').is_subword_of(Word('ababa')) False
sage: Word().is_subword_of(Word('123')) True sage: Word('123').is_subword_of(Word('3211333213233321')) True sage: Word('321').is_subword_of(Word('11122212112122133111222332')) False
- is_suffix(other)#
Return
True
ifself
is a suffix ofother
, andFalse
otherwise.EXAMPLES:
sage: w = Word('0123456789') sage: y = Word('56789') sage: y.is_suffix(w) True sage: w.is_suffix(y) False sage: Word('579').is_suffix(w) False sage: Word().is_suffix(y) True sage: w.is_suffix(Word()) False sage: Word().is_suffix(Word()) True
- is_symmetric(f=None)#
Return
True
ifself
is symmetric (orf
-symmetric), andFalse
otherwise.A word is symmetric (resp. \(f\)-symmetric) if it is the product of two palindromes (resp. \(f\)-palindromes). See [BHNR2004] and [DeLuca2006].
INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
).
EXAMPLES:
sage: Word('abbabab').is_symmetric() True sage: Word('ababa').is_symmetric() True sage: Word('aababaabba').is_symmetric() False sage: Word('aabbbaababba').is_symmetric() False sage: f = WordMorphism('a->b,b->a') sage: Word('aabbbaababba').is_symmetric(f) True
- is_tangent()#
Tell whether
self
is a tangent word.The finite word
self
must be defined on a two-letter alphabet.A binary word is said to be tangent if it can appear in infinitely many cutting sequences of a smooth curve, where each cutting sequence is observed on a progressively smaller grid.
This class of words strictly contains the class of \(1\)-balanced words, and is strictly contained in the class of \(2\)-balanced words.
This method runs in linear time.
OUTPUT:
boolean – the result
EXAMPLES:
sage: w = Word('01110110110111011101',alphabet='01') sage: w.is_tangent() True
Some tangent words may not be balanced:
sage: Word('aabb',alphabet='ab').is_balanced() False sage: Word('aabb',alphabet='ab').is_tangent() True
Some \(2\)-balanced words may not be tangent:
sage: Word('aaabb',alphabet='ab').is_tangent() False sage: Word('aaabb',alphabet='ab').is_balanced(2) True
Famous words:
sage: words.FibonacciWord()[:100].is_tangent() True sage: words.ThueMorseWord()[:1000].is_tangent() True sage: words.KolakoskiWord()[:1000].is_tangent() False
See [Mon2010].
AUTHOR:
Thierry Monteil
- is_yamanouchi(n=None)#
Return whether
self
is Yamanouchi.A word \(w\) is Yamanouchi if, when read from right to left, it always has weakly more \(i\)’s than \(i+1\)’s for all \(i\) that appear in \(w\).
INPUT:
n
– (optional) an integer specifying the maximal letter in the alphabet
EXAMPLES:
sage: w = Word([1,2,4,3,2,2,2]) sage: w.is_yamanouchi() False sage: w = Word([2,3,4,3,1,2,1,1,2,1]) sage: w.is_yamanouchi() True sage: w = Word([3,1]) sage: w.is_yamanouchi(n=3) False sage: w.is_yamanouchi() True sage: w = Word([3,1],alphabet=[1,2,3]) sage: w.is_yamanouchi() False sage: w = Word([2,1,1,2]) sage: w.is_yamanouchi() False
- iterated_left_palindromic_closure(f=None)#
Return the iterated left (
f
-)palindromic closure ofself
.INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
).
OUTPUT:
word – the left iterated
f
-palindromic closure ofself
.EXAMPLES:
sage: Word('123').iterated_left_palindromic_closure() word: 3231323 sage: f = WordMorphism('a->b,b->a') sage: Word('ab').iterated_left_palindromic_closure(f=f) word: abbaab sage: Word('aab').iterated_left_palindromic_closure(f=f) word: abbaabbaab
- lacunas(f=None)#
Return the list of all the lacunas of
self
.A lacuna is a position in a word where the longest (\(f\)-)palindromic suffix is not unioccurrent (see [BMBL2008]).
INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
). The default value corresponds to usual palindromes, i.e.,f
equal to the identity.
OUTPUT:
a list – list of all the lacunas of self
EXAMPLES:
sage: w = Word([0,1,1,2,3,4,5,1,13,3]) sage: w.lacunas() [7, 9] sage: words.ThueMorseWord()[:100].lacunas() [8, 9, 24, 25, 32, 33, 34, 35, 36, 37, 38, 39, 96, 97, 98, 99] sage: f = WordMorphism({0:[1],1:[0]}) sage: words.ThueMorseWord()[:50].lacunas(f) [0, 2, 4, 12, 16, 17, 18, 19, 48, 49]
- last_position_dict()#
Return a dictionary that contains the last position of each letter in
self
.EXAMPLES:
sage: Word('1231232').last_position_dict() {'1': 3, '2': 6, '3': 5}
- left_special_factors(n=None)#
Return the left special factors (of length
n
).A factor \(u\) of a word \(w\) is left special if there are two distinct letters \(a\) and \(b\) such that \(au\) and \(bu\) are factors of \(w\).
INPUT:
n
– integer (optional, default:None
). IfNone
, it returns all left special factors.
OUTPUT:
a list of words
EXAMPLES:
sage: alpha, beta, x = 0.54, 0.294, 0.1415 sage: w = words.CodingOfRotationWord(alpha, beta, x)[:40] sage: for i in range(5): ....: print("{} {}".format(i, sorted(w.left_special_factors(i)))) 0 [word: ] 1 [word: 0] 2 [word: 00, word: 01] 3 [word: 000, word: 010] 4 [word: 0000, word: 0101]
- left_special_factors_iterator(n=None)#
Return an iterator over the left special factors (of length
n
).A factor \(u\) of a word \(w\) is left special if there are two distinct letters \(a\) and \(b\) such that \(au\) and \(bu\) are factors of \(w\).
INPUT:
n
– integer (optional, default:None
). IfNone
, it returns an iterator over all left special factors.
EXAMPLES:
sage: alpha, beta, x = 0.54, 0.294, 0.1415 sage: w = words.CodingOfRotationWord(alpha, beta, x)[:40] sage: sorted(w.left_special_factors_iterator(3)) [word: 000, word: 010] sage: sorted(w.left_special_factors_iterator(4)) [word: 0000, word: 0101] sage: sorted(w.left_special_factors_iterator(5)) [word: 00000, word: 01010]
- length()#
Return the length of
self
.
- length_border()#
Return the length of the border of
self
.The border of a word is the longest word that is both a proper prefix and a proper suffix of
self
.EXAMPLES:
sage: Word('121').length_border() 1 sage: Word('1').length_border() 0 sage: Word('1212').length_border() 2 sage: Word('111').length_border() 2 sage: Word().length_border() is None True
- length_maximal_palindrome(j, m=None, f=None)#
Return the length of the longest palindrome centered at position
j
.INPUT:
j
– rational, position of the symmetry axis of the palindrome. Must return an integer when doubled. It is an integer when the center of the palindrome is a letter.m
– integer (default:None
), minimal length of palindrome, if known. The parity ofm
can’t be the same as the parity of2j
.f
– involution (default:None
), on the alphabet. It must be callable on letters as well as words (e.g.WordMorphism
).
OUTPUT:
length of the longest
f
-palindrome centered at positionj
EXAMPLES:
sage: Word('01001010').length_maximal_palindrome(3/2) 0 sage: Word('01101001').length_maximal_palindrome(3/2) 4 sage: Word('01010').length_maximal_palindrome(j=3, f='0->1,1->0') 0 sage: Word('01010').length_maximal_palindrome(j=2.5, f='0->1,1->0') 4 sage: Word('0222220').length_maximal_palindrome(3, f='0->1,1->0,2->2') 5
sage: w = Word('abcdcbaxyzzyx') sage: w.length_maximal_palindrome(3) 7 sage: w.length_maximal_palindrome(3, 3) 7 sage: w.length_maximal_palindrome(3.5) 0 sage: w.length_maximal_palindrome(9.5) 6 sage: w.length_maximal_palindrome(9.5, 2) 6
- lengths_maximal_palindromes(f=None)#
Return the length of maximal palindromes centered at each position.
INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
).
OUTPUT:
a list – The length of the maximal palindrome (or
f
-palindrome) with a given symmetry axis (letter or space between two letters).EXAMPLES:
sage: Word('01101001').lengths_maximal_palindromes() [0, 1, 0, 1, 4, 1, 0, 3, 0, 3, 0, 1, 4, 1, 0, 1, 0] sage: Word('00000').lengths_maximal_palindromes() [0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0] sage: Word('0').lengths_maximal_palindromes() [0, 1, 0] sage: Word('').lengths_maximal_palindromes() [0] sage: Word().lengths_maximal_palindromes() [0] sage: f = WordMorphism('a->b,b->a') sage: Word('abbabaab').lengths_maximal_palindromes(f) [0, 0, 2, 0, 0, 0, 2, 0, 8, 0, 2, 0, 0, 0, 2, 0, 0]
- lengths_unioccurrent_lps(f=None)#
Return the list of the lengths of the unioccurrent longest (
f
)-palindromic suffixes (lps) for each non-empty prefix ofself.
No unioccurrent lps are indicated byNone
.It corresponds to the function \(H_w\) defined in [BMBL2008] and [BMBFLR2008].
INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
). The default value corresponds to usual palindromes, i.e.,f
equal to the identity.
OUTPUT:
a list – list of the length of the unioccurrent longest palindromic suffix (lps) for each non-empty prefix of
self
. No unioccurrent lps are indicated byNone
.EXAMPLES:
sage: w = Word([0,1,1,2,3,4,5,1,13,3]) sage: w.lengths_unioccurrent_lps() [1, 1, 2, 1, 1, 1, 1, None, 1, None] sage: f = words.FibonacciWord()[:20] sage: f.lengths_unioccurrent_lps() == f.lps_lengths()[1:] True sage: t = words.ThueMorseWord() sage: t[:20].lengths_unioccurrent_lps() [1, 1, 2, 4, 3, 3, 2, 4, None, None, 6, 8, 10, 12, 14, 16, 6, 8, 10, 12] sage: f = WordMorphism({1:[0],0:[1]}) sage: t[:15].lengths_unioccurrent_lps(f) [None, 2, None, 2, None, 4, 6, 8, 4, 6, 4, 6, None, 4, 6]
- letters()#
Return the list of letters that appear in this word, listed in the order of first appearance.
EXAMPLES:
sage: Word([0,1,1,0,1,0,0,1]).letters() [0, 1] sage: Word("cacao").letters() ['c', 'a', 'o']
- longest_backward_extension(x, y)#
Compute the length of the longest factor of
self
that ends atx
and that matches a factor that ends aty
.INPUT:
x
,y
– positions inself
EXAMPLES:
sage: w = Word('0011001') sage: w.longest_backward_extension(6, 2) 3 sage: w.longest_backward_extension(1, 4) 1 sage: w.longest_backward_extension(1, 3) 0
The method also accepts negative positions indicating the distance from the end of the word (in order to be consist with how negative indices work with lists). For instance, for a word of length \(7\), using positions \(6\) and \(-5\) is the same as using positions \(6\) and \(2\):
sage: w.longest_backward_extension(6, -5) 3 sage: w.longest_backward_extension(-6, 4) 1
- longest_common_subword(other)#
Return a longest subword of
self
andother
.A subword of a word is a subset of the word’s letters, read in the order in which they appear in the word.
For more information, see Wikipedia article Longest_common_subsequence_problem.
INPUT:
other
– a word
ALGORITHM:
For any indices \(i,j\), we compute the longest common subword
lcs[i,j]
ofself[:i]
andother[:j]
. This can be easily obtained as the longest oflcs[i-1,j]
lcs[i,j-1]
lcs[i-1,j-1]+self[i]
ifself[i]==other[j]
EXAMPLES:
sage: v1 = Word("abc") sage: v2 = Word("ace") sage: v1.longest_common_subword(v2) word: ac sage: w1 = Word("1010101010101010101010101010101010101010") sage: w2 = Word("0011001100110011001100110011001100110011") sage: w1.longest_common_subword(w2) word: 00110011001100110011010101010
See also
- longest_common_suffix(other)#
Return the longest common suffix of
self
andother
.EXAMPLES:
sage: w = Word('112345678') sage: u = Word('1115678') sage: w.longest_common_suffix(u) word: 5678 sage: u.longest_common_suffix(u) word: 1115678 sage: u.longest_common_suffix(w) word: 5678 sage: w.longest_common_suffix(w) word: 112345678 sage: y = Word('549332345') sage: w.longest_common_suffix(y) word:
- longest_forward_extension(x, y)#
Compute the length of the longest factor of
self
that starts atx
and that matches a factor that starts aty
.INPUT:
x
,y
– positions inself
EXAMPLES:
sage: w = Word('0011001') sage: w.longest_forward_extension(0, 4) 3 sage: w.longest_forward_extension(0, 2) 0
The method also accepts negative positions indicating the distance from the end of the word (in order to be consist with how negative indices work with lists). For instance, for a word of length \(7\), using positions \(-3\) and \(2\) is the same as using positions \(4\) and \(2\):
sage: w.longest_forward_extension(1, -2) 2 sage: w.longest_forward_extension(4, -3) 3
- lps(f=None, l=None)#
Return the longest palindromic (or
f
-palindromic) suffix ofself
.INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
).l
– integer (default:None
) the length of the longest palindrome suffix of``self[:-1]``
, if known.
OUTPUT:
word – If
f
isNone
, the longest palindromic suffix ofself
; otherwise, the longestf
-palindromic suffix ofself
.EXAMPLES:
sage: Word('0111').lps() word: 111 sage: Word('011101').lps() word: 101 sage: Word('6667').lps() word: 7 sage: Word('abbabaab').lps() word: baab sage: Word().lps() word: sage: f = WordMorphism('a->b,b->a') sage: Word('abbabaab').lps(f=f) word: abbabaab sage: w = Word('33412321') sage: w.lps(l=3) word: 12321 sage: Y = Word sage: w = Y('01101001') sage: w.lps(l=2) word: 1001 sage: w.lps() word: 1001 sage: w.lps(l=None) word: 1001 sage: Y().lps(l=2) Traceback (most recent call last): ... IndexError: list index out of range sage: v = Word('abbabaab') sage: pal = v[:0] sage: for i in range(1, v.length()+1): ....: pal = v[:i].lps(l=pal.length()) ....: pal word: a word: b word: bb word: abba word: bab word: aba word: aa word: baab sage: f = WordMorphism('a->b,b->a') sage: v = Word('abbabaab') sage: pal = v[:0] sage: for i in range(1, v.length()+1): ....: pal = v[:i].lps(f=f, l=pal.length()) ....: pal word: word: ab word: word: ba word: ab word: baba word: bbabaa word: abbabaab
- lps_lengths(f=None)#
Return the length of the longest palindromic suffix of each prefix.
INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
).
OUTPUT:
a list – The length of the longest palindromic (or
f
-palindromic) suffix of each prefix ofself
.EXAMPLES:
sage: Word('01101001').lps_lengths() [0, 1, 1, 2, 4, 3, 3, 2, 4] sage: Word('00000').lps_lengths() [0, 1, 2, 3, 4, 5] sage: Word('0').lps_lengths() [0, 1] sage: Word('').lps_lengths() [0] sage: Word().lps_lengths() [0] sage: f = WordMorphism('a->b,b->a') sage: Word('abbabaab').lps_lengths(f) [0, 0, 2, 0, 2, 2, 4, 6, 8]
- lyndon_factorization()#
Return the Lyndon factorization of
self
.The Lyndon factorization of a finite word \(w\) is the unique factorization of \(w\) as a non-increasing product of Lyndon words, i.e., \(w = l_1\cdots l_n\) where each \(l_i\) is a Lyndon word and \(l_1\geq \cdots \geq l_n\). See for instance [Duv1983].
OUTPUT:
the list \([l_1, \ldots, l_n]\) of factors obtained
EXAMPLES:
sage: Word('010010010001000').lyndon_factorization() (01, 001, 001, 0001, 0, 0, 0) sage: Words('10')('010010010001000').lyndon_factorization() (0, 10010010001000) sage: Word('abbababbaababba').lyndon_factorization() (abb, ababb, aababb, a) sage: Words('ba')('abbababbaababba').lyndon_factorization() (a, bbababbaaba, bba) sage: Word([1,2,1,3,1,2,1]).lyndon_factorization() (1213, 12, 1)
- major_index(final_descent=False)#
Return the major index of
self
.The major index of a word \(w\) is the sum of the descents of \(w\).
With the
final_descent
option, the last position of a non-empty word is also considered as a descent.See also
EXAMPLES:
sage: w = Word([2,1,3,3,2]) sage: w.major_index() 5 sage: w = Word([2,1,3,3,2]) sage: w.major_index(final_descent=True) 10
- minimal_conjugate()#
Return the lexicographically minimal conjugate of this word (see Wikipedia article Lexicographically_minimal_string_rotation).
EXAMPLES:
sage: Word('213').minimal_conjugate() word: 132 sage: Word('11').minimal_conjugate() word: 11 sage: Word('12112').minimal_conjugate() word: 11212 sage: Word('211').minimal_conjugate() word: 112 sage: Word('211211211').minimal_conjugate() word: 112112112
- minimal_period()#
Return the period of
self
.Let \(A\) be an alphabet. An integer \(p\geq 1\) is a period of a word \(w=a_1a_2\cdots a_n\) where \(a_i\in A\) if \(a_i=a_{i+p}\) for \(i=1,\ldots,n-p\). The smallest period of \(w\) is called the period of \(w\). See Chapter 1 of [Lot2002].
EXAMPLES:
sage: Word('aba').minimal_period() 2 sage: Word('abab').minimal_period() 2 sage: Word('ababa').minimal_period() 2 sage: Word('ababaa').minimal_period() 5 sage: Word('ababac').minimal_period() 6 sage: Word('aaaaaa').minimal_period() 1 sage: Word('a').minimal_period() 1 sage: Word().minimal_period() 1
- nb_factor_occurrences_in(other)#
Return the number of times
self
appears as a factor inother
.Warning
This method is deprecated since 2020 and will be removed in a later version of SageMath. Use
number_of_factor_occurrences()
instead.EXAMPLES:
sage: Word('123').nb_factor_occurrences_in(Word('112332312313112332121123')) doctest:warning ... DeprecationWarning: f.nb_factor_occurrences_in(w) is deprecated. Use w.number_of_factor_occurrences(f) instead. See https://github.com/sagemath/sage/issues/30187 for details. 4 sage: Word('321').nb_factor_occurrences_in(Word('11233231231311233221123')) 0
An error is raised for the empty word:
sage: Word().nb_factor_occurrences_in(Word('123')) Traceback (most recent call last): ... NotImplementedError: The factor must be non empty
- nb_subword_occurrences_in(other)#
Return the number of times
self
appears inother
as a subword.This corresponds to the notion of \(binomial coefficient\) of two finite words whose properties are presented in the chapter of Lothaire’s book written by Sakarovitch and Simon [Lot1997].
Warning
This method is deprecated since 2020 and will be removed in a later version of SageMath. Use
number_of_subword_occurrences()
instead.INPUT:
other
– finite word
EXAMPLES:
sage: tm = words.ThueMorseWord() sage: u = Word([0,1,0,1]) sage: u.nb_subword_occurrences_in(tm[:1000]) doctest:warning ... DeprecationWarning: f.nb_subword_occurrences_in(w) is deprecated. Use w.number_of_subword_occurrences(f) instead. See https://github.com/sagemath/sage/issues/30187 for details. 2604124996 sage: u = Word([0,1,0,1,1,0]) sage: u.nb_subword_occurrences_in(tm[:100]) 20370432
Note
This code, based on [MSSY2001], actually compute the number of occurrences of all prefixes of
self
as subwords in all prefixes ofother
. In particular, its complexity is bounded bylen(self) * len(other)
.
- number_of_factor_occurrences(other)#
Return the number of times
other
appears as a factor inself
.INPUT:
other
– a non empty wordEXAMPLES:
sage: w = Word('112332312313112332121123') sage: w.number_of_factor_occurrences(Word('123')) 4 sage: w = Word('11233231231311233221123') sage: w.number_of_factor_occurrences(Word('321')) 0
sage: Word().number_of_factor_occurrences(Word('123')) 0
An error is raised for the empty word:
sage: Word('123').number_of_factor_occurrences(Word()) Traceback (most recent call last): ... NotImplementedError: The factor must be non empty
- number_of_factors(n=None, algorithm='suffix tree')#
Count the number of distinct factors of
self
.INPUT:
n
– an integer, orNone
.algorithm
– string (default:'suffix tree'
), takes the following values:'suffix tree'
– construct and use the suffix tree of the word'naive'
– algorithm uses a sliding window
OUTPUT:
If
n
is an integer, returns the number of distinct factors of lengthn
. Ifn
isNone
, returns the total number of distinct factors.EXAMPLES:
sage: w = Word([1,2,1,2,3]) sage: w.number_of_factors() 13 sage: [w.number_of_factors(i) for i in range(6)] [1, 3, 3, 3, 2, 1]
sage: w = words.ThueMorseWord()[:100] sage: [w.number_of_factors(i) for i in range(10)] [1, 2, 4, 6, 10, 12, 16, 20, 22, 24]
sage: Word('1213121').number_of_factors() 22 sage: Word('1213121').number_of_factors(1) 3
sage: Word('a'*100).number_of_factors() 101 sage: Word('a'*100).number_of_factors(77) 1
sage: Word().number_of_factors() 1 sage: Word().number_of_factors(17) 0
sage: blueberry = Word("blueberry") sage: blueberry.number_of_factors() 43 sage: [blueberry.number_of_factors(i) for i in range(10)] [1, 6, 8, 7, 6, 5, 4, 3, 2, 1]
- number_of_inversions()#
Return the number of inversions in
self
.An inversion of a word \(w = w_1 \ldots w_n\) is a pair of indices \((i, j)\) with \(i < j\) and \(w_i > w_j\).
See also
EXAMPLES:
sage: w = Word([2,1,3,3,2]) sage: w.number_of_inversions() 3
- number_of_left_special_factors(n)#
Return the number of left special factors of length
n
.A factor \(u\) of a word \(w\) is left special if there are two distinct letters \(a\) and \(b\) such that \(au\) and \(bu\) are factors of \(w\).
INPUT:
n
– integer
OUTPUT:
a non-negative integer
EXAMPLES:
sage: w = words.FibonacciWord()[:100] sage: [w.number_of_left_special_factors(i) for i in range(10)] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sage: w = words.ThueMorseWord()[:100] sage: [w.number_of_left_special_factors(i) for i in range(10)] [1, 2, 2, 4, 2, 4, 4, 2, 2, 4]
- number_of_letter_occurrences(letter)#
Return the number of occurrences of
letter
inself
.INPUT:
letter
- a letter
OUTPUT:
integer
EXAMPLES:
sage: w = Word('abbabaab') sage: w.number_of_letter_occurrences('a') 4 sage: w.number_of_letter_occurrences('ab') 0
This methods is equivalent to
list(w).count(letter)
andtuple(w).count(letter)
, thuscount
is an alias for the methodnumber_of_letter_occurrences
:sage: list(w).count('a') 4 sage: w.count('a') 4
But notice that if
s
andw
are strings,Word(s).count(w)
counts the number occurrences ofw
as a letter inWord(s)
which is not the same ass.count(w)
which counts the number of occurrences of the stringw
insides
:sage: s = 'abbabaab' sage: s.count('ab') 3 sage: Word(s).count('ab') 0
- number_of_right_special_factors(n)#
Return the number of right special factors of length
n
.A factor \(u\) of a word \(w\) is right special if there are two distinct letters \(a\) and \(b\) such that \(ua\) and \(ub\) are factors of \(w\).
INPUT:
n
– integer
OUTPUT:
a non-negative integer
EXAMPLES:
sage: w = words.FibonacciWord()[:100] sage: [w.number_of_right_special_factors(i) for i in range(10)] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sage: w = words.ThueMorseWord()[:100] sage: [w.number_of_right_special_factors(i) for i in range(10)] [1, 2, 2, 4, 2, 4, 4, 2, 2, 4]
- number_of_subword_occurrences(other)#
Return the number of times
other
appears inself
as a subword.This corresponds to the notion of \(binomial coefficient\) of two finite words whose properties are presented in the chapter of Lothaire’s book written by Sakarovitch and Simon [Lot1997].
INPUT:
other
– finite word
EXAMPLES:
sage: tm = words.ThueMorseWord() sage: u = Word([0,1,0,1]) sage: tm[:1000].number_of_subword_occurrences(u) 2604124996 sage: u = Word([0,1,0,1,1,0]) sage: tm[:100].number_of_subword_occurrences(u) 20370432
Note
This code, based on [MSSY2001], actually compute the number of occurrences of all prefixes of
self
as subwords in all prefixes ofother
. In particular, its complexity is bounded bylen(self) * len(other)
.
- order()#
Return the order of
self
.Let \(p(w)\) be the period of a word \(w\). The positive rational number \(|w|/p(w)\) is the order of \(w\). See Chapter 8 of [Lot2002].
OUTPUT:
rational – the order
EXAMPLES:
sage: Word('abaaba').order() 2 sage: Word('ababaaba').order() 8/5 sage: Word('a').order() 1 sage: Word('aa').order() 2 sage: Word().order() 0
- overlap_partition(other, delay=0, p=None, involution=None)#
Return the partition of the alphabet induced by the overlap of
self
andother
with the givendelay
.The partition of the alphabet is given by the equivalence relation obtained from the symmetric, reflexive and transitive closure of the set of pairs of letters \(R_{u,v,d} = \{ (u_k, v_{k-d}) : 0 \leq k < n, 0\leq k-d < m \}\) where \(u = u_0 u_1 \cdots u_{n-1}\), \(v = v_0v_1\cdots v_{m-1}\) are two words on the alphabet \(A\) and \(d\) is an integer.
The equivalence relation defined by \(R\) is inspired from [Lab2008].
INPUT:
other
– word on the same alphabet asself
delay
– integer (default:0
)p
– disjoint sets data structure (optional, default:None
), a partition of the alphabet into disjoint sets to start with. IfNone
, each letter start in distinct equivalence classes.involution
– callable (optional, default:None
), an involution on the alphabet. Ifinvolution
is notNone
, the relation \(R_{u,v,d} \cup R_{involution(u),involution(v),d}\) is considered.
OUTPUT:
a disjoint set data structure
EXAMPLES:
sage: W = Words(list('abc012345')) sage: u = W('abc') sage: v = W('01234') sage: u.overlap_partition(v) {{'0', 'a'}, {'1', 'b'}, {'2', 'c'}, {'3'}, {'4'}, {'5'}} sage: u.overlap_partition(v, 2) {{'0', 'c'}, {'1'}, {'2'}, {'3'}, {'4'}, {'5'}, {'a'}, {'b'}} sage: u.overlap_partition(v, -1) {{'0'}, {'1', 'a'}, {'2', 'b'}, {'3', 'c'}, {'4'}, {'5'}}
You can re-use the same disjoint set and do more than one overlap:
sage: p = u.overlap_partition(v, 2) sage: p {{'0', 'c'}, {'1'}, {'2'}, {'3'}, {'4'}, {'5'}, {'a'}, {'b'}} sage: u.overlap_partition(v, 1, p) {{'0', '1', 'b', 'c'}, {'2'}, {'3'}, {'4'}, {'5'}, {'a'}}
The function
overlap_partition
can be used to study equations on words. For example, if a word \(w\) overlaps itself with delay \(d\), then \(d\) is a period of \(w\):sage: W = Words(range(20)) sage: w = W(range(14)); w word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13 sage: d = 5 sage: p = w.overlap_partition(w, d) sage: m = WordMorphism(p.element_to_root_dict()) sage: w2 = m(w); w2 word: 56789567895678 sage: w2.minimal_period() == d True
If a word is equal to its reversal, then it is a palindrome:
sage: W = Words(range(20)) sage: w = W(range(17)); w word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 sage: p = w.overlap_partition(w.reversal(), 0) sage: m = WordMorphism(p.element_to_root_dict()) sage: w2 = m(w); w2 word: 01234567876543210 sage: w2.parent() Finite words over {0, 1, 2, 3, 4, 5, 6, 7, 8, 17, 18, 19} sage: w2.is_palindrome() True
If the reversal of a word \(w\) is factor of its square \(w^2\), then \(w\) is symmetric, i.e. the product of two palindromes:
sage: W = Words(range(10)) sage: w = W(range(10)); w word: 0123456789 sage: p = (w*w).overlap_partition(w.reversal(), 4) sage: m = WordMorphism(p.element_to_root_dict()) sage: w2 = m(w); w2 word: 0110456654 sage: w2.is_symmetric() True
If the image of the reversal of a word \(w\) under an involution \(f\) is factor of its square \(w^2\), then \(w\) is \(f\)-symmetric:
sage: W = Words([-11,-9,..,11]) sage: w = W([1,3,..,11]) sage: w word: 1,3,5,7,9,11 sage: inv = lambda x:-x sage: f = WordMorphism(dict( (a, inv(a)) for a in W.alphabet())) sage: p = (w*w).overlap_partition(f(w).reversal(), 2, involution=f) sage: m = WordMorphism(p.element_to_root_dict()) sage: m(w) word: 1,-1,5,7,-7,-5 sage: m(w).is_symmetric(f) True
- palindrome_prefixes()#
Return a list of all palindrome prefixes of
self
.OUTPUT:
a list – A list of all palindrome prefixes of
self
.EXAMPLES:
sage: w = Word('abaaba') sage: w.palindrome_prefixes() [word: , word: a, word: aba, word: abaaba] sage: w = Word('abbbbbbbbbb') sage: w.palindrome_prefixes() [word: , word: a]
- palindromes(f=None)#
Return the set of all palindromic (or
f
-palindromic) factors ofself
.INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
).
OUTPUT:
a set – If
f
isNone
, the set of all palindromic factors ofself
; otherwise, the set of allf
-palindromic factors ofself
.EXAMPLES:
sage: sorted(Word('01101001').palindromes()) [word: , word: 0, word: 00, word: 010, word: 0110, word: 1, word: 1001, word: 101, word: 11] sage: sorted(Word('00000').palindromes()) [word: , word: 0, word: 00, word: 000, word: 0000, word: 00000] sage: sorted(Word('0').palindromes()) [word: , word: 0] sage: sorted(Word('').palindromes()) [word: ] sage: sorted(Word().palindromes()) [word: ] sage: f = WordMorphism('a->b,b->a') sage: sorted(Word('abbabaab').palindromes(f)) [word: , word: ab, word: abbabaab, word: ba, word: baba, word: bbabaa]
- palindromic_closure(side='right', f=None)#
Return the shortest palindrome having
self
as a prefix (or as a suffix ifside
is'left'
).See [DeLuca2006].
INPUT:
side
–'right'
or'left'
(default:'right'
) the direction of the closuref
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
).
OUTPUT:
a word – If
f
isNone
, the right palindromic closure ofself
; otherwise, the rightf
-palindromic closure ofself
. Ifside
is'left'
, the left palindromic closure.EXAMPLES:
sage: Word('1233').palindromic_closure() word: 123321 sage: Word('12332').palindromic_closure() word: 123321 sage: Word('0110343').palindromic_closure() word: 01103430110 sage: Word('0110343').palindromic_closure(side='left') word: 3430110343 sage: Word('01105678').palindromic_closure(side='left') word: 876501105678 sage: w = Word('abbaba') sage: w.palindromic_closure() word: abbababba
sage: f = WordMorphism('a->b,b->a') sage: w.palindromic_closure(f=f) word: abbabaab sage: w.palindromic_closure(f=f, side='left') word: babaabbaba
- palindromic_complexity(n)#
Return the number of distinct palindromic factors of length
n
ofself
.INPUT:
n
– the length of the factors.
EXAMPLES:
sage: w = words.FibonacciWord()[:100] sage: [w.palindromic_complexity(i) for i in range(20)] [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
sage: w = words.ThueMorseWord()[:1000] sage: [w.palindromic_complexity(i) for i in range(20)] [1, 2, 2, 2, 2, 0, 4, 0, 4, 0, 4, 0, 4, 0, 2, 0, 2, 0, 4, 0]
- palindromic_lacunas_study(f=None)#
Return interesting statistics about longest (
f
-)palindromic suffixes and lacunas ofself
(see [BMBL2008] and [BMBFLR2008]).Note that a word \(w\) has at most \(|w| + 1\) different palindromic factors (see [DJP2001]). For \(f\)-palindromes (or pseudopalindromes or theta-palindromes), the maximum number of \(f\)-palindromic factors is \(|w|+1-g_f(w)\), where \(g_f(w)\) is the number of pairs \(\{a, f(a)\}\) such that \(a\) is a letter, \(a\) is not equal to \(f(a)\), and \(a\) or \(f(a)\) occurs in \(w\), see [Star2011].
INPUT:
f
– involution (default:None
) on the alphabet ofself
. It must be callable on letters as well as words (e.g.WordMorphism
). The default value corresponds to usual palindromes, i.e.,f
equal to the identity.
OUTPUT:
list
– list of the length of the longest palindromic suffix (lps) for each non-empty prefix ofself
list
– list of all the lacunas, i.e. positions where there is no unioccurrent lpsset
– set of palindromic factors ofself
EXAMPLES:
sage: a,b,c = Word('abbabaabbaab').palindromic_lacunas_study() sage: a [1, 1, 2, 4, 3, 3, 2, 4, 2, 4, 6, 8] sage: b [8, 9] sage: c # random order set([word: , word: b, word: bab, word: abba, word: bb, word: aa, word: baabbaab, word: baab, word: aba, word: aabbaa, word: a])
sage: f = WordMorphism('a->b,b->a') sage: a,b,c = Word('abbabaab').palindromic_lacunas_study(f=f) sage: a [0, 2, 0, 2, 2, 4, 6, 8] sage: b [0, 2, 4] sage: c # random order set([word: , word: ba, word: baba, word: ab, word: bbabaa, word: abbabaab]) sage: c == set([Word(), Word('ba'), Word('baba'), Word('ab'), Word('bbabaa'), Word('abbabaab')]) True
- periods(divide_length=False)#
Return a list containing the periods of
self
between \(1\) and \(n - 1\), where \(n\) is the length ofself
.INPUT:
divide_length
– boolean (default:False
). When set toTrue
, then only periods that divide the length ofself
are considered.
OUTPUT:
a list of positive integers
EXAMPLES:
sage: w = Word('ababab') sage: w.periods() [2, 4] sage: w.periods(divide_length=True) [2] sage: w = Word('ababa') sage: w.periods() [2, 4] sage: w.periods(divide_length=True) []
- phi()#
Apply the phi function to
self
and return the result. This is the word obtained by taking the first letter of the words obtained by iterating delta onself
.OUTPUT:
a word – the result of the phi function
EXAMPLES:
sage: W = Words([1, 2]) sage: W([2,2,1,1,2,1,2,2,1,2,2,1,1,2]).phi() word: 222222 sage: W([2,1,2,2,1,2,2,1,2,1]).phi() word: 212113 sage: W().phi() word: sage: Word([2,1,2,2,1,2,2,1,2,1]).phi() word: 212113 sage: Word([2,3,1,1,2,1,2,3,1,2,2,3,1,2]).phi() word: 21215 sage: Word("aabbabaabaabba").phi() word: a22222 sage: w = Word([2,3,1,1,2,1,2,3,1,2,2,3,1,2])
See [BL2003] and [BDLV2006].
- phi_inv(W=None)#
Apply the inverse of the phi function to
self
.INPUT:
self
– a word over the integersW
– a parent object of words defined over integers
OUTPUT:
a word – the inverse of the phi function
EXAMPLES:
sage: W = Words([1, 2]) sage: W([2, 2, 2, 2, 1, 2]).phi_inv() word: 22112122 sage: W([2, 2, 2]).phi_inv(Words([2, 3])) word: 2233
- prefix_function_table()#
Return a vector containing the length of the proper prefix-suffixes for all the non-empty prefixes of
self
.EXAMPLES:
sage: Word('121321').prefix_function_table() [0, 0, 1, 0, 0, 1] sage: Word('1241245').prefix_function_table() [0, 0, 0, 1, 2, 3, 0] sage: Word().prefix_function_table() []
- primitive()#
Return the primitive of
self
.EXAMPLES:
sage: Word('12312').primitive() word: 12312 sage: Word('121212').primitive() word: 12
- primitive_length()#
Return the length of the primitive of
self
.EXAMPLES:
sage: Word('1231').primitive_length() 4 sage: Word('121212').primitive_length() 2
- quasiperiods()#
Return the quasiperiods of
self
as a list ordered from shortest to longest.Let \(w\) be a finite or infinite word. A quasiperiod of \(w\) is a proper factor \(u\) of \(w\) such that the occurrences of \(u\) in \(w\) entirely cover \(w\), i.e., every position of \(w\) falls within some occurrence of \(u\) in \(w\). See for instance [AE1993], [Mar2004], and [GLR2008].
EXAMPLES:
sage: Word('abaababaabaababaaba').quasiperiods() [word: aba, word: abaaba, word: abaababaaba] sage: Word('abaaba').quasiperiods() [word: aba] sage: Word('abacaba').quasiperiods() []
- rauzy_graph(n)#
Return the Rauzy graph of the factors of length
n
ofself
.The vertices are the factors of length \(n\) and there is an edge from \(u\) to \(v\) if \(ua = bv\) is a factor of length \(n+1\) for some letters \(a\) and \(b\).
INPUT:
n
– integer
EXAMPLES:
sage: w = Word(range(10)); w word: 0123456789 sage: g = w.rauzy_graph(3); g # optional - sage.graphs Looped digraph on 8 vertices sage: WordOptions(identifier='') sage: g.vertices(sort=True) # optional - sage.graphs [012, 123, 234, 345, 456, 567, 678, 789] sage: g.edges(sort=True) # optional - sage.graphs [(012, 123, 3), (123, 234, 4), (234, 345, 5), (345, 456, 6), (456, 567, 7), (567, 678, 8), (678, 789, 9)] sage: WordOptions(identifier='word: ')
sage: f = words.FibonacciWord()[:100] sage: f.rauzy_graph(8) # optional - sage.graphs Looped digraph on 9 vertices
sage: w = Word('1111111') sage: g = w.rauzy_graph(3) # optional - sage.graphs sage: g.edges(sort=True) # optional - sage.graphs [(word: 111, word: 111, word: 1)]
sage: w = Word('111') sage: for i in range(5): w.rauzy_graph(i) # optional - sage.graphs Looped multi-digraph on 1 vertex Looped digraph on 1 vertex Looped digraph on 1 vertex Looped digraph on 1 vertex Looped digraph on 0 vertices
Multi-edges are allowed for the empty word:
sage: W = Words('abcde') sage: w = W('abc') sage: w.rauzy_graph(0) # optional - sage.graphs Looped multi-digraph on 1 vertex sage: _.edges(sort=True) # optional - sage.graphs [(word: , word: , word: a), (word: , word: , word: b), (word: , word: , word: c)]
- reduced_rauzy_graph(n)#
Return the reduced Rauzy graph of order
n
ofself
.INPUT:
n
– a non-negative integer. Every vertex of a reduced Rauzy graph of ordern
is a factor of lengthn
ofself
.
OUTPUT:
a looped multi-digraph
DEFINITION:
For infinite periodic words (resp. for finite words of type \(u^i u[0:j]\)), the reduced Rauzy graph of order \(n\) (resp. for \(n\) smaller or equal to \((i-1)|u|+j\)) is the directed graph whose unique vertex is the prefix \(p\) of length \(n\) of
self
and which has an only edge which is a loop on \(p\) labelled by \(w[n+1:|w|] p\) where \(w\) is the unique return word to \(p\).In other cases, it is the directed graph defined as followed. Let \(G_n\) be the Rauzy graph of order \(n\) of self. The vertices are the vertices of \(G_n\) that are either special or not prolongable to the right or to the left. For each couple (\(u\), \(v\)) of such vertices and each directed path in \(G_n\) from \(u\) to \(v\) that contains no other vertices that are special, there is an edge from \(u\) to \(v\) in the reduced Rauzy graph of order \(n\) whose label is the label of the path in \(G_n\).
Note
In the case of infinite recurrent non-periodic words, this definition corresponds to the following one that can be found in [BDLGZ2009] and [BPS2008] where a simple path is a path that begins with a special factor, ends with a special factor and contains no other vertices that are special:
The reduced Rauzy graph of factors of length \(n\) is obtained from \(G_n\) by replacing each simple path \(P=v_1 v_2 ... v_{\ell}\) with an edge \(v_1 v_{\ell}\) whose label is the concatenation of the labels of the edges of \(P\).
EXAMPLES:
sage: w = Word(range(10)); w word: 0123456789 sage: g = w.reduced_rauzy_graph(3); g # optional - sage.graphs Looped multi-digraph on 2 vertices sage: g.vertices(sort=True) # optional - sage.graphs [word: 012, word: 789] sage: g.edges(sort=True) # optional - sage.graphs [(word: 012, word: 789, word: 3456789)]
For the Fibonacci word:
sage: f = words.FibonacciWord()[:100] sage: g = f.reduced_rauzy_graph(8);g # optional - sage.graphs Looped multi-digraph on 2 vertices sage: g.vertices(sort=True) # optional - sage.graphs [word: 01001010, word: 01010010] sage: g.edges(sort=True) # optional - sage.graphs [(word: 01001010, word: 01010010, word: 010), (word: 01010010, word: 01001010, word: 01010), (word: 01010010, word: 01001010, word: 10)]
For periodic words:
sage: from itertools import cycle sage: w = Word(cycle('abcd'))[:100] sage: g = w.reduced_rauzy_graph(3) # optional - sage.graphs sage: g.edges(sort=True) # optional - sage.graphs [(word: abc, word: abc, word: dabc)]
sage: w = Word('111') sage: for i in range(5): w.reduced_rauzy_graph(i) # optional - sage.graphs Looped digraph on 1 vertex Looped digraph on 1 vertex Looped digraph on 1 vertex Looped multi-digraph on 1 vertex Looped multi-digraph on 0 vertices
For ultimately periodic words:
sage: sigma = WordMorphism('a->abcd,b->cd,c->cd,d->cd') sage: w = sigma.fixed_point('a')[:100]; w word: abcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd... sage: g = w.reduced_rauzy_graph(5) # optional - sage.graphs sage: g.vertices(sort=True) # optional - sage.graphs [word: abcdc, word: cdcdc] sage: g.edges(sort=True) # optional - sage.graphs [(word: abcdc, word: cdcdc, word: dc), (word: cdcdc, word: cdcdc, word: dc)]
AUTHOR:
Julien Leroy (March 2010): initial version
- return_words(fact)#
Return the set of return words of
fact
inself
.This is the set of all factors starting by the given factor and ending just before the next occurrence of this factor. See [Dur1998] and [HZ1999].
INPUT:
fact
– a non-empty finite word
OUTPUT:
a Python set of finite words
EXAMPLES:
sage: Word('21331233213231').return_words(Word('2')) {word: 213, word: 21331, word: 233} sage: Word().return_words(Word('213')) set() sage: Word('121212').return_words(Word('1212')) {word: 12}
sage: TM = words.ThueMorseWord()[:1000] sage: sorted(TM.return_words(Word([0]))) [word: 0, word: 01, word: 011]
- return_words_derivate(fact)#
Return the word generated by mapping a letter to each occurrence of the return words for the given factor dropping any dangling prefix and suffix. See for instance [Dur1998].
EXAMPLES:
sage: Word('12131221312313122').return_words_derivate(Word('1')) word: 123242
- rev_lex_less(other)#
Return
True
if the wordself
is reverse lexicographically less thanother
.EXAMPLES:
sage: Word([1,2,4]).rev_lex_less(Word([1,3,2])) True sage: Word([3,2,1]).rev_lex_less(Word([1,2,3])) False
- reversal()#
Return the reversal of
self
.EXAMPLES:
sage: Word('124563').reversal() word: 365421
- rfind(sub, start=0, end=None)#
Return the index of the last occurrence of
sub
inself
, such thatsub
is contained withinself[start:end]
. Return-1
on failure.INPUT:
sub
– string, list, tuple or word to search for.start
– non-negative integer (default:0
) specifying the position at which the search must stop.end
– non-negative integer (default:None
) specifying the position from which to start the search. IfNone
, then the search is performed up to the end of the string.
OUTPUT:
a non-negative integer or
-1
EXAMPLES:
sage: w = Word([0,1,0,0,1]) sage: w.rfind(Word([0,1])) 3
The
sub
parameter can also be a list or a tuple:sage: w.rfind([0,1]) 3 sage: w.rfind((0,1)) 3
Examples using the argument
start
andend
:sage: w.rfind(Word([0,1]), end=4) 0 sage: w.rfind(Word([0,1]), end=5) 3 sage: w.rfind(Word([0,0]), start=2, end=5) 2 sage: w.rfind(Word([0,0]), start=3, end=5) -1
Instances of
Word_str
handle string inputs as well:sage: w = Word('abac') sage: w.rfind('a') 2 sage: w.rfind(Word('a')) 2 sage: w.rfind([0,1]) -1
- right_special_factors(n=None)#
Return the right special factors (of length
n
).A factor \(u\) of a word \(w\) is right special if there are two distinct letters \(a\) and \(b\) such that \(ua\) and \(ub\) are factors of \(w\).
INPUT:
n
– integer (optional, default:None
). IfNone
, it returns all right special factors.
OUTPUT:
a list of words
EXAMPLES:
sage: w = words.ThueMorseWord()[:30] sage: for i in range(5): ....: print("{} {}".format(i, sorted(w.right_special_factors(i)))) 0 [word: ] 1 [word: 0, word: 1] 2 [word: 01, word: 10] 3 [word: 001, word: 010, word: 101, word: 110] 4 [word: 0110, word: 1001]
- right_special_factors_iterator(n=None)#
Return an iterator over the right special factors (of length
n
).A factor \(u\) of a word \(w\) is right special if there are two distinct letters \(a\) and \(b\) such that \(ua\) and \(ub\) are factors of \(w\).
INPUT:
n
– integer (optional, default:None
). IfNone
, it returns an iterator over all right special factors.
EXAMPLES:
sage: alpha, beta, x = 0.61, 0.54, 0.3 sage: w = words.CodingOfRotationWord(alpha, beta, x)[:40] sage: sorted(w.right_special_factors_iterator(3)) [word: 010, word: 101] sage: sorted(w.right_special_factors_iterator(4)) [word: 0101, word: 1010] sage: sorted(w.right_special_factors_iterator(5)) [word: 00101, word: 11010]
- robinson_schensted()#
Return the semistandard tableau and standard tableau pair obtained by running the Robinson-Schensted algorithm on
self
.This can also be done by running
RSK()
onself
.EXAMPLES:
sage: Word([1,1,3,1,2,3,1]).robinson_schensted() [[[1, 1, 1, 1, 3], [2], [3]], [[1, 2, 3, 5, 6], [4], [7]]]
- schuetzenberger_involution(n=None)#
Return the Schützenberger involution of the word
self
, which is obtained by reverting the word and then complementing all letters within the underlying ordered alphabet. Ifn
is specified, the underlying alphabet is assumed to be \([1,2,\ldots,n]\). If no alphabet is specified, \(n\) is the maximal letter appearing inself
.INPUT:
self
– a wordn
– an integer specifying the maximal letter in the alphabet (optional)
OUTPUT:
a word, the Schützenberger involution of
self
EXAMPLES:
sage: w = Word([9,7,4,1,6,2,3]) sage: v = w.schuetzenberger_involution(); v word: 7849631 sage: v.parent() Finite words over Set of Python objects of class 'object' sage: w = Word([1,2,3],alphabet=[1,2,3,4,5]) sage: v = w.schuetzenberger_involution();v word: 345 sage: v.parent() Finite words over {1, 2, 3, 4, 5} sage: w = Word([1,2,3]) sage: v = w.schuetzenberger_involution(n=5);v word: 345 sage: v.parent() Finite words over Set of Python objects of class 'object' sage: w = Word([11,32,69,2,53,1,2,3,18,41]) sage: w.schuetzenberger_involution() word: 29,52,67,68,69,17,68,1,38,59 sage: w = Word([],alphabet=[1,2,3,4,5]) sage: w.schuetzenberger_involution() word: sage: w = Word([]) sage: w.schuetzenberger_involution() word:
- shifted_shuffle(other, shift=None)#
Return the combinatorial class representing the shifted shuffle product between words
self
andother
. This is the same as the shuffle product ofself
with the word obtained fromother
by incrementing its values (i.e. its letters) by the givenshift
.INPUT:
other
– finite word over the integersshift
– integer orNone
(default:None
) added to each letter ofother
. Whenshift
isNone
, it is replaced byself.length()
OUTPUT:
combinatorial class of shifted shuffle products of
self
andother
EXAMPLES:
sage: w = Word([0,1,1]) sage: sp = w.shifted_shuffle(w); sp Shuffle product of word: 011 and word: 344 sage: sp = w.shifted_shuffle(w, 2); sp Shuffle product of word: 011 and word: 233 sage: sp.cardinality() 20 sage: WordOptions(identifier='') sage: sp.list() [011233, 012133, 012313, 012331, 021133, 021313, 021331, 023113, 023131, 023311, 201133, 201313, 201331, 203113, 203131, 203311, 230113, 230131, 230311, 233011] sage: WordOptions(identifier='word: ') sage: y = Word('aba') sage: y.shifted_shuffle(w,2) Traceback (most recent call last): ... ValueError: for shifted shuffle, words must only contain integers as letters
- shuffle(other, overlap=0)#
Return the combinatorial class representing the shuffle product between words
self
andother
. This consists of all words of lengthself.length()+other.length()
that have bothself
andother
as subwords.If
overlap
is non-zero, then the combinatorial class representing the shuffle product with overlaps is returned. The calculation of the shift in each overlap is done relative to the order of the alphabet. For example, \(a\) shifted by \(a\) is \(b\) in the alphabet \([a, b, c]\) and \(0\) shifted by \(1\) in \([0, 1, 2, 3]\) is \(2\).INPUT:
other
– finite wordoverlap
– (default:0
) integer orTrue
OUTPUT:
combinatorial class of shuffle product of
self
andother
EXAMPLES:
sage: ab = Word("ab") sage: cd = Word("cd") sage: sp = ab.shuffle(cd); sp Shuffle product of word: ab and word: cd sage: sp.cardinality() 6 sage: sp.list() [word: abcd, word: acbd, word: acdb, word: cabd, word: cadb, word: cdab] sage: w = Word([0,1]) sage: u = Word([2,3]) sage: w.shuffle(w) Shuffle product of word: 01 and word: 01 sage: u.shuffle(u) Shuffle product of word: 23 and word: 23 sage: w.shuffle(u) Shuffle product of word: 01 and word: 23 sage: sp2 = w.shuffle(u,2); sp2 Overlapping shuffle product of word: 01 and word: 23 with 2 overlaps sage: list(sp2) [word: 24]
- squares()#
Returns a set of all distinct squares of
self
.EXAMPLES:
sage: sorted(Word('cacao').squares()) [word: , word: caca] sage: sorted(Word('1111').squares()) [word: , word: 11, word: 1111] sage: w = Word('00110011010') sage: sorted(w.squares()) [word: , word: 00, word: 00110011, word: 01100110, word: 1010, word: 11]
- standard_factorization()#
Return the standard factorization of
self
.The standard factorization of a word \(w\) of length greater than \(1\) is the factorization \(w = uv\) where \(v\) is the longest proper suffix of \(w\) that is a Lyndon word.
Note that if \(w\) is a Lyndon word of length greater than \(1\) with standard factorization \(w = uv\), then \(u\) and \(v\) are also Lyndon words and \(u < v\).
See for instance [CFL1958], [Duv1983] and [Lot2002].
INPUT:
self
– finite word of length greater than \(1\)
OUTPUT:
\(2\)-tuple \((u, v)\)
EXAMPLES:
sage: Words('01')('0010110011').standard_factorization() (word: 001011, word: 0011) sage: Words('123')('1223312').standard_factorization() (word: 12233, word: 12) sage: Word([3,2,1]).standard_factorization() (word: 32, word: 1)
sage: w = Word('0010110011',alphabet='01') sage: w.standard_factorization() (word: 001011, word: 0011) sage: w = Word('0010110011',alphabet='10') sage: w.standard_factorization() (word: 001011001, word: 1) sage: w = Word('1223312',alphabet='123') sage: w.standard_factorization() (word: 12233, word: 12)
- standard_permutation()#
Return the standard permutation of the word
self
on the ordered alphabet. It is defined as the permutation with exactly the same inversions asself
. Equivalently, it is the permutation of minimal length whose inverse sortsself
.EXAMPLES:
sage: w = Word([1,2,3,2,2,1]); w word: 123221 sage: p = w.standard_permutation(); p [1, 3, 6, 4, 5, 2] sage: v = Word(p.inverse().action(w)); v word: 112223 sage: [q for q in Permutations(w.length()) ....: if q.length() <= p.length() and ....: q.inverse().action(w) == list(v)] [[1, 3, 6, 4, 5, 2]]
sage: w = Words([1,2,3])([1,2,3,2,2,1,2,1]); w word: 12322121 sage: p = w.standard_permutation(); p [1, 4, 8, 5, 6, 2, 7, 3] sage: Word(p.inverse().action(w)) word: 11122223
sage: w = Words([3,2,1])([1,2,3,2,2,1,2,1]); w word: 12322121 sage: p = w.standard_permutation(); p [6, 2, 1, 3, 4, 7, 5, 8] sage: Word(p.inverse().action(w)) word: 32222111
sage: w = Words('ab')('abbaba'); w word: abbaba sage: p = w.standard_permutation(); p [1, 4, 5, 2, 6, 3] sage: Word(p.inverse().action(w)) word: aaabbb
sage: w = Words('ba')('abbaba'); w word: abbaba sage: p = w.standard_permutation(); p [4, 1, 2, 5, 3, 6] sage: Word(p.inverse().action(w)) word: bbbaaa
- sturmian_desubstitute_as_possible()#
Sturmian-desubstitute the word
self
as much as possible.The finite word
self
must be defined on a two-letter alphabet or use at most two letters.It can be Sturmian desubstituted if one letter appears isolated: the Sturmian desubstitution consists in removing one letter per run of the non-isolated letter. The accelerated Sturmian desubstitution consists in removing a run equal to the length of the shortest inner run from any run of the non-isolated letter (including possible leading and trailing runs even if they have shorter length). The (accelerated) Sturmian desubstitution is done as much as possible. A word is a factor of a Sturmian word if, and only if, the result is the empty word.
OUTPUT:
a finite word defined on a two-letter alphabet
EXAMPLES:
sage: u = Word('10111101101110111',alphabet='01') ; u word: 10111101101110111 sage: v = u.sturmian_desubstitute_as_possible() ; v word: 01100101 sage: v == v.sturmian_desubstitute_as_possible() True sage: Word('azaazaaazaaazaazaaaz', alphabet='az').sturmian_desubstitute_as_possible() word:
AUTHOR:
Thierry Monteil
- subword_complementaries(other)#
Return the possible complementaries
other
minusself
ifself
is a subword ofother
(empty list otherwise). The complementary is made of all the letters that are inother
once we removed the letters ofself
. There can be more than one.To check whether
self
is a subword ofother
(without knowing its complementaries), useself.is_subword_of(other)
, and to count the number of occurrences ofself
inother
, useother.number_of_subword_occurrences(self)
.INPUT:
other
– finite word
OUTPUT:
list of all the complementary subwords of
self
inother
.
EXAMPLES:
sage: Word('tamtam').subword_complementaries(Word('ta')) [] sage: Word('mta').subword_complementaries(Word('tamtam')) [word: tam] sage: Word('ta').subword_complementaries(Word('tamtam')) [word: mtam, word: amtm, word: tamm] sage: Word('a').subword_complementaries(Word('a')) [word: ]
- suffix_tree()#
Alias for
implicit_suffix_tree()
.EXAMPLES:
sage: Word('abbabaab').suffix_tree() Implicit Suffix Tree of the word: abbabaab
- suffix_trie()#
Return the suffix trie of
self
.The suffix trie of a finite word \(w\) is a data structure representing the factors of \(w\). It is a tree whose edges are labelled with letters of \(w\), and whose leafs correspond to suffixes of \(w\).
Type
sage.combinat.words.suffix_trees.SuffixTrie?
for more information.EXAMPLES:
sage: w = Word("cacao") sage: w.suffix_trie() Suffix Trie of the word: cacao
sage: w = Word([0,1,0,1,1]) sage: w.suffix_trie() Suffix Trie of the word: 01011
- swap(i, j=None)#
Return the word \(w\) with entries at positions
i
andj
swapped. By default,j = i+1
.EXAMPLES:
sage: Word([1,2,3]).swap(0,2) word: 321 sage: Word([1,2,3]).swap(1) word: 132 sage: Word("abba").swap(1,-1) word: aabb
- swap_decrease(i)#
Return the word with positions
i
andi+1
exchanged ifself[i] < self[i+1]
. Otherwise, it returnsself
.EXAMPLES:
sage: w = Word([1,3,2]) sage: w.swap_decrease(0) word: 312 sage: w.swap_decrease(1) word: 132 sage: w.swap_decrease(1) is w True sage: Words("ab")("abba").swap_decrease(0) word: baba sage: Words("ba")("abba").swap_decrease(0) word: abba
- swap_increase(i)#
Return the word with positions
i
andi+1
exchanged ifself[i] > self[i+1]
. Otherwise, it returnsself
.EXAMPLES:
sage: w = Word([1,3,2]) sage: w.swap_increase(1) word: 123 sage: w.swap_increase(0) word: 132 sage: w.swap_increase(0) is w True sage: Words("ab")("abba").swap_increase(0) word: abba sage: Words("ba")("abba").swap_increase(0) word: baba
- to_integer_list()#
Return a list of integers from
[0,1,...,self.length()-1]
in the same relative order as the letters inself
in the parent.EXAMPLES:
sage: from itertools import count sage: w = Word('abbabaab') sage: w.to_integer_list() [0, 1, 1, 0, 1, 0, 0, 1] sage: w = Word(iter("cacao"), length="finite") sage: w.to_integer_list() [1, 0, 1, 0, 2] sage: w = Words([3,2,1])([2,3,3,1]) sage: w.to_integer_list() [1, 0, 0, 2]
- to_integer_word()#
Return a word over the alphabet
[0,1,...,self.length()-1]
whose letters are in the same relative order as the letters ofself
in the parent.EXAMPLES:
sage: from itertools import count sage: w = Word('abbabaab') sage: w.to_integer_word() word: 01101001 sage: w = Word(iter("cacao"), length="finite") sage: w.to_integer_word() word: 10102 sage: w = Words([3,2,1])([2,3,3,1]) sage: w.to_integer_word() word: 1002
- to_monoid_element()#
Return
self
as an element of the free monoid with the same alphabet asself
.EXAMPLES:
sage: w = Word('aabb') sage: w.to_monoid_element() a^2*b^2 sage: W = Words('abc') sage: w = W(w) sage: w.to_monoid_element() a^2*b^2
- to_ordered_set_partition()#
Return the ordered set partition correspond to
self
.If \(w\) is a finite word of length \(n\), then the corresponding ordered set partition is an ordered set partition \((P_1, P_2, \ldots, P_k)\) of \(\{1, 2, \ldots, n\}\), where each block \(P_i\) is the set of positions at which the \(i\)-th smallest letter occurring in \(w\) occurs in \(w\).
EXAMPLES:
sage: w = Word('abbabaab') sage: w.to_ordered_set_partition() [{1, 4, 6, 7}, {2, 3, 5, 8}] sage: Word([-10, 3, -10, 2]).to_ordered_set_partition() [{1, 3}, {4}, {2}] sage: Word([]).to_ordered_set_partition() [] sage: Word('aaaaa').to_ordered_set_partition() [{1, 2, 3, 4, 5}]
- topological_entropy(n)#
Return the topological entropy for the factors of length
n
.The topological entropy of a sequence \(u\) is defined as the exponential growth rate of the complexity of \(u\) as the length increases: \(H_{top}(u)=\lim_{n\to\infty}\frac{\log_d(p_u(n))}{n}\) where \(d\) denotes the cardinality of the alphabet and \(p_u(n)\) is the complexity function, i.e. the number of factors of length \(n\) in the sequence \(u\) [Fog2002].
INPUT:
self
– a word defined over a finite alphabetn
– positive integer
OUTPUT:
real number (a symbolic expression)
EXAMPLES:
sage: W = Words([0, 1]) sage: w = W([0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1]) sage: t = w.topological_entropy(3); t # optional - sage.symbolic 1/3*log(7)/log(2) sage: n(t) # optional - sage.symbolic 0.935784974019201
sage: w = words.ThueMorseWord()[:100] sage: topo = w.topological_entropy sage: for i in range(0, 41, 5): # optional - sage.symbolic ....: print("{} {}".format(i, n(topo(i), digits=5))) 0 1.0000 5 0.71699 10 0.48074 15 0.36396 20 0.28774 25 0.23628 30 0.20075 35 0.17270 40 0.14827
If no alphabet is specified, an error is raised:
sage: w = Word(range(20)) sage: w.topological_entropy(3) Traceback (most recent call last): ... TypeError: The word must be defined over a finite alphabet
The following is ok:
sage: W = Words(range(20)) sage: w = W(range(20)) sage: w.topological_entropy(3) # optional - sage.symbolic 1/3*log(18)/log(20)
- sage.combinat.words.finite_word.evaluation_dict(w)#
Return a dictionary keyed by the letters occurring in
w
with values the number of occurrences of the letter.INPUT:
w
– a word
- sage.combinat.words.finite_word.word_to_ordered_set_partition(w)#
Return the ordered set partition corresponding to a finite word \(w\).
If \(w\) is a finite word of length \(n\), then the corresponding ordered set partition is an ordered set partition \((P_1, P_2, \ldots, P_k)\) of \(\{1, 2, \ldots, n\}\), where each block \(P_i\) is the set of positions at which the \(i\)-th smallest letter occurring in \(w\) occurs in \(w\). (Positions are \(1\)-based.)
This is the same functionality that
to_ordered_set_partition()
provides, but without the wrapping: The input \(w\) can be given as a list or tuple, not necessarily as a word; and the output is returned as a list of lists (which are the blocks of the ordered set partition in increasing order), not as an ordered set partition.EXAMPLES:
sage: from sage.combinat.words.finite_word import word_to_ordered_set_partition sage: word_to_ordered_set_partition([3, 6, 3, 1]) [[4], [1, 3], [2]] sage: word_to_ordered_set_partition((1, 3, 3, 7)) [[1], [2, 3], [4]] sage: word_to_ordered_set_partition("noob") [[4], [1], [2, 3]] sage: word_to_ordered_set_partition(Word("hell")) [[2], [1], [3, 4]] sage: word_to_ordered_set_partition([1]) [[1]] sage: word_to_ordered_set_partition([]) []