Word classes¶
AUTHORS:
Arnaud Bergeron
Amy Glen
Sébastien Labbé
Franco Saliola
- class sage.combinat.words.word.FiniteWord_callable(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable
,FiniteWord_class
Finite word represented by a callable.
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).EXAMPLES:
sage: f = lambda n : 3 if n > 8 else 6 sage: w = Word(f, length=30, caching=False) sage: w word: 666666666333333333333333333333 sage: w.is_symmetric() True
>>> from sage.all import * >>> f = lambda n : Integer(3) if n > Integer(8) else Integer(6) >>> w = Word(f, length=Integer(30), caching=False) >>> w word: 666666666333333333333333333333 >>> w.is_symmetric() True
- class sage.combinat.words.word.FiniteWord_callable_with_caching(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable_with_caching
,FiniteWord_class
Finite word represented by a callable (with caching).
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).EXAMPLES:
sage: f = lambda n : n % 3 sage: w = Word(f, length=32) sage: w word: 01201201201201201201201201201201 sage: w.border() word: 01201201201201201201201201201
>>> from sage.all import * >>> f = lambda n : n % Integer(3) >>> w = Word(f, length=Integer(32)) >>> w word: 01201201201201201201201201201201 >>> w.border() word: 01201201201201201201201201201
- class sage.combinat.words.word.FiniteWord_char[source]¶
Bases:
WordDatatype_char
,FiniteWord_class
Finite word represented by an array
unsigned char *
(i.e. integers between 0 and 255).For any word
w
, typew.<TAB>
to see the functions that can be applied tow
.EXAMPLES:
sage: W = Words(range(20)) sage: w = W(list(range(1, 10)) * 2) sage: type(w) <class 'sage.combinat.words.word.FiniteWord_char'> sage: w word: 123456789123456789 sage: w.is_palindrome() False sage: (w*w[::-1]).is_palindrome() True sage: (w[:-1:]*w[::-1]).is_palindrome() True sage: w.is_lyndon() False sage: W(list(range(10)) + [10, 10]).is_lyndon() True sage: w.is_square_free() False sage: w[:-1].is_square_free() True sage: u = W([randint(0,10) for i in range(10)]) sage: (u*u).is_square() True sage: (u*u*u).is_cube() True sage: len(w.factor_set()) 127 sage: w.rauzy_graph(5) # needs sage.graphs Looped digraph on 9 vertices sage: u = W([1,2,3]) sage: w.first_occurrence(u) 0 sage: w.first_occurrence(u, start=1) 9
>>> from sage.all import * >>> W = Words(range(Integer(20))) >>> w = W(list(range(Integer(1), Integer(10))) * Integer(2)) >>> type(w) <class 'sage.combinat.words.word.FiniteWord_char'> >>> w word: 123456789123456789 >>> w.is_palindrome() False >>> (w*w[::-Integer(1)]).is_palindrome() True >>> (w[:-Integer(1):]*w[::-Integer(1)]).is_palindrome() True >>> w.is_lyndon() False >>> W(list(range(Integer(10))) + [Integer(10), Integer(10)]).is_lyndon() True >>> w.is_square_free() False >>> w[:-Integer(1)].is_square_free() True >>> u = W([randint(Integer(0),Integer(10)) for i in range(Integer(10))]) >>> (u*u).is_square() True >>> (u*u*u).is_cube() True >>> len(w.factor_set()) 127 >>> w.rauzy_graph(Integer(5)) # needs sage.graphs Looped digraph on 9 vertices >>> u = W([Integer(1),Integer(2),Integer(3)]) >>> w.first_occurrence(u) 0 >>> w.first_occurrence(u, start=Integer(1)) 9
- class sage.combinat.words.word.FiniteWord_iter(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter
,FiniteWord_class
Finite word represented by an iterator.
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).EXAMPLES:
sage: w = Word(iter(range(10)), caching=False) sage: w word: 0123456789 sage: w.finite_differences() word: 111111111
>>> from sage.all import * >>> w = Word(iter(range(Integer(10))), caching=False) >>> w word: 0123456789 >>> w.finite_differences() word: 111111111
- class sage.combinat.words.word.FiniteWord_iter_with_caching(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter_with_caching
,FiniteWord_class
Finite word represented by an iterator (with caching).
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).EXAMPLES:
sage: w = Word(iter('abcdef')) sage: w.conjugate(2) word: cdefab
>>> from sage.all import * >>> w = Word(iter('abcdef')) >>> w.conjugate(Integer(2)) word: cdefab
- class sage.combinat.words.word.FiniteWord_list[source]¶
Bases:
WordDatatype_list
,FiniteWord_class
Finite word represented by a Python list.
For any word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).EXAMPLES:
sage: w = Word(range(10)) sage: w.iterated_right_palindromic_closure() word: 0102010301020104010201030102010501020103...
>>> from sage.all import * >>> w = Word(range(Integer(10))) >>> w.iterated_right_palindromic_closure() word: 0102010301020104010201030102010501020103...
- class sage.combinat.words.word.FiniteWord_morphic(parent, morphism, letter, coding=None, length=+Infinity)[source]¶
Bases:
WordDatatype_morphic
,FiniteWord_class
Finite morphic word.
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).EXAMPLES:
sage: m = WordMorphism("a->ab,b->") sage: w = m.fixed_point("a") sage: w word: ab
>>> from sage.all import * >>> m = WordMorphism("a->ab,b->") >>> w = m.fixed_point("a") >>> w word: ab
- class sage.combinat.words.word.FiniteWord_str[source]¶
Bases:
WordDatatype_str
,FiniteWord_class
Finite word represented by a Python str.
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).EXAMPLES:
sage: w = Word('abcdef') sage: w.is_square() False
>>> from sage.all import * >>> w = Word('abcdef') >>> w.is_square() False
- class sage.combinat.words.word.FiniteWord_tuple[source]¶
Bases:
WordDatatype_tuple
,FiniteWord_class
Finite word represented by a Python tuple.
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).EXAMPLES:
sage: w = Word(()) sage: w.is_empty() True
>>> from sage.all import * >>> w = Word(()) >>> w.is_empty() True
- class sage.combinat.words.word.InfiniteWord_callable(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable
,InfiniteWord_class
Infinite word represented by a callable.
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).Infinite words behave like a Python list : they can be sliced using square braquets to define for example a prefix or a factor.
EXAMPLES:
sage: w = Word(lambda n:n, caching=False) sage: w word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,... sage: w.iterated_right_palindromic_closure() word: 0102010301020104010201030102010501020103...
>>> from sage.all import * >>> w = Word(lambda n:n, caching=False) >>> w word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,... >>> w.iterated_right_palindromic_closure() word: 0102010301020104010201030102010501020103...
- class sage.combinat.words.word.InfiniteWord_callable_with_caching(parent, callable, length=None)[source]¶
Bases:
WordDatatype_callable_with_caching
,InfiniteWord_class
Infinite word represented by a callable (with caching).
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).Infinite words behave like a Python list : they can be sliced using square braquets to define for example a prefix or a factor.
EXAMPLES:
sage: w = Word(lambda n:n) sage: factor = w[4:13] sage: factor word: 4,5,6,7,8,9,10,11,12
>>> from sage.all import * >>> w = Word(lambda n:n) >>> factor = w[Integer(4):Integer(13)] >>> factor word: 4,5,6,7,8,9,10,11,12
- class sage.combinat.words.word.InfiniteWord_iter(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter
,InfiniteWord_class
Infinite word represented by an iterable.
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).Infinite words behave like a Python list : they can be sliced using square braquets to define for example a prefix or a factor.
EXAMPLES:
sage: from itertools import chain, cycle sage: w = Word(chain('letsgo', cycle('forever')), caching=False) sage: w word: letsgoforeverforeverforeverforeverforeve... sage: prefix = w[:100] sage: prefix word: letsgoforeverforeverforeverforeverforeve... sage: prefix.is_lyndon() False
>>> from sage.all import * >>> from itertools import chain, cycle >>> w = Word(chain('letsgo', cycle('forever')), caching=False) >>> w word: letsgoforeverforeverforeverforeverforeve... >>> prefix = w[:Integer(100)] >>> prefix word: letsgoforeverforeverforeverforeverforeve... >>> prefix.is_lyndon() False
- class sage.combinat.words.word.InfiniteWord_iter_with_caching(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter_with_caching
,InfiniteWord_class
Infinite word represented by an iterable (with caching).
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).Infinite words behave like a Python list : they can be sliced using square braquets to define for example a prefix or a factor.
EXAMPLES:
sage: from itertools import cycle sage: w = Word(cycle([9,8,4])) sage: w word: 9849849849849849849849849849849849849849... sage: prefix = w[:23] sage: prefix word: 98498498498498498498498 sage: prefix.minimal_period() 3
>>> from sage.all import * >>> from itertools import cycle >>> w = Word(cycle([Integer(9),Integer(8),Integer(4)])) >>> w word: 9849849849849849849849849849849849849849... >>> prefix = w[:Integer(23)] >>> prefix word: 98498498498498498498498 >>> prefix.minimal_period() 3
- class sage.combinat.words.word.InfiniteWord_morphic(parent, morphism, letter, coding=None, length=+Infinity)[source]¶
Bases:
WordDatatype_morphic
,InfiniteWord_class
Morphic word of infinite length.
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).Infinite words behave like a Python list : they can be sliced using square braquets to define for example a prefix or a factor.
EXAMPLES:
sage: m = WordMorphism('a->ab,b->a') sage: w = m.fixed_point('a') sage: w word: abaababaabaababaababaabaababaabaababaaba...
>>> from sage.all import * >>> m = WordMorphism('a->ab,b->a') >>> w = m.fixed_point('a') >>> w word: abaababaabaababaababaabaababaabaababaaba...
- sage.combinat.words.word.Word(data=None, alphabet=None, length=None, datatype=None, caching=True, RSK_data=None)[source]¶
Construct a word.
INPUT:
data
– (default:None
) list, string, tuple, iterator, free monoid element,None
(shorthand for[]
), or a callable defined on[0,1,...,length]
alphabet
– any argument accepted by Wordslength
– (default:None
) this is dependent on the type of data. It is ignored for words defined by lists, strings, tuples, etc., because they have a naturally defined length. For callables, this defines the domain of definition, which is assumed to be[0, 1, 2, ..., length-1]
. For iterators: Infinity if you know the iterator will not terminate (default);'unknown'
if you do not know whether the iterator terminates;'finite'
if you know that the iterator terminates, but do not know the length.datatype
– (default:None
)None
,'list'
,'str'
,'tuple'
,'iter'
,'callable'
; ifNone
, then the function tries to guess this from the datacaching
– boolean (default:True
); whether to keep a cache of the letters computed by an iterator or callableRSK_data
– (default:None
) semistandard and a standard Young tableau to run the inverse RSK bijection on
Note
Be careful when defining words using callables and iterators. It appears that islice does not pickle correctly causing various errors when reloading. Also, most iterators do not support copying and should not support pickling by extension.
EXAMPLES:
Empty word:
sage: Word() word:
>>> from sage.all import * >>> Word() word:
Word with string:
sage: Word("abbabaab") word: abbabaab
>>> from sage.all import * >>> Word("abbabaab") word: abbabaab
Word with string constructed from other types:
sage: Word([0,1,1,0,1,0,0,1], datatype='str') word: 01101001 sage: Word((0,1,1,0,1,0,0,1), datatype='str') word: 01101001
>>> from sage.all import * >>> Word([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1)], datatype='str') word: 01101001 >>> Word((Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1)), datatype='str') word: 01101001
Word with list:
sage: Word([0,1,1,0,1,0,0,1]) word: 01101001
>>> from sage.all import * >>> Word([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1)]) word: 01101001
Word with list constructed from other types:
sage: Word("01101001", datatype='list') word: 01101001 sage: Word((0,1,1,0,1,0,0,1), datatype='list') word: 01101001
>>> from sage.all import * >>> Word("01101001", datatype='list') word: 01101001 >>> Word((Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1)), datatype='list') word: 01101001
Word with tuple:
sage: Word((0,1,1,0,1,0,0,1)) word: 01101001
>>> from sage.all import * >>> Word((Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1))) word: 01101001
Word with tuple constructed from other types:
sage: Word([0,1,1,0,1,0,0,1], datatype='tuple') word: 01101001 sage: Word("01101001", datatype='str') word: 01101001
>>> from sage.all import * >>> Word([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1)], datatype='tuple') word: 01101001 >>> Word("01101001", datatype='str') word: 01101001
Word with iterator:
sage: from itertools import count sage: Word(count()) word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,... sage: Word(iter("abbabaab")) # iterators default to infinite words word: abbabaab sage: Word(iter("abbabaab"), length='unknown') word: abbabaab sage: Word(iter("abbabaab"), length='finite') word: abbabaab
>>> from sage.all import * >>> from itertools import count >>> Word(count()) word: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,... >>> Word(iter("abbabaab")) # iterators default to infinite words word: abbabaab >>> Word(iter("abbabaab"), length='unknown') word: abbabaab >>> Word(iter("abbabaab"), length='finite') word: abbabaab
Word with function (a ‘callable’):
sage: f = lambda n : add(Integer(n).digits(2)) % 2 sage: Word(f) word: 0110100110010110100101100110100110010110... sage: Word(f, length=8) word: 01101001
>>> from sage.all import * >>> f = lambda n : add(Integer(n).digits(Integer(2))) % Integer(2) >>> Word(f) word: 0110100110010110100101100110100110010110... >>> Word(f, length=Integer(8)) word: 01101001
Word over a string with a parent:
sage: w = Word("abbabaab", alphabet='abc'); w word: abbabaab sage: w.parent() Finite words over {'a', 'b', 'c'}
>>> from sage.all import * >>> w = Word("abbabaab", alphabet='abc'); w word: abbabaab >>> w.parent() Finite words over {'a', 'b', 'c'}
Word from a free monoid element:
sage: M.<x,y,z> = FreeMonoid(3) sage: Word(x^3*y*x*z^2*x) word: xxxyxzzx
>>> from sage.all import * >>> M = FreeMonoid(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = M._first_ngens(3) >>> Word(x**Integer(3)*y*x*z**Integer(2)*x) word: xxxyxzzx
The default parent is the combinatorial class of all words:
sage: w = Word("abbabaab"); w word: abbabaab sage: w.parent() Finite words over Set of Python objects of class 'object'
>>> from sage.all import * >>> w = Word("abbabaab"); w word: abbabaab >>> w.parent() Finite words over Set of Python objects of class 'object'
We can also input a semistandard tableau and a standard tableau to obtain a word from the inverse RSK algorithm using the
RSK_data
option:sage: p = Tableau([[1,2,2],[3]]); q = Tableau([[1,2,4],[3]]) sage: Word(RSK_data=[p, q]) word: 1322
>>> from sage.all import * >>> p = Tableau([[Integer(1),Integer(2),Integer(2)],[Integer(3)]]); q = Tableau([[Integer(1),Integer(2),Integer(4)],[Integer(3)]]) >>> Word(RSK_data=[p, q]) word: 1322
- class sage.combinat.words.word.Word_iter(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter
,Word_class
Word of unknown length (finite or infinite) represented by an iterable.
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).Words behave like a Python list : they can be sliced using square braquets to define for example a prefix or a factor.
EXAMPLES:
sage: w = Word(iter([1,1,4,9]*1000), length='unknown', caching=False) sage: w word: 1149114911491149114911491149114911491149... sage: w.delta() word: 2112112112112112112112112112112112112112...
>>> from sage.all import * >>> w = Word(iter([Integer(1),Integer(1),Integer(4),Integer(9)]*Integer(1000)), length='unknown', caching=False) >>> w word: 1149114911491149114911491149114911491149... >>> w.delta() word: 2112112112112112112112112112112112112112...
- class sage.combinat.words.word.Word_iter_with_caching(parent, iter, length=None)[source]¶
Bases:
WordDatatype_iter_with_caching
,Word_class
Word of unknown length (finite or infinite) represented by an iterable (with caching).
For such word \(w\), type
w.
and hit Tab key to see the list of functions defined on \(w\).Words behave like a Python list : they can be sliced using square braquets to define for example a prefix or a factor.
EXAMPLES:
sage: w = Word(iter([1,2,3]*1000), length='unknown') sage: w word: 1231231231231231231231231231231231231231... sage: w.finite_differences(mod=2) word: 1101101101101101101101101101101101101101...
>>> from sage.all import * >>> w = Word(iter([Integer(1),Integer(2),Integer(3)]*Integer(1000)), length='unknown') >>> w word: 1231231231231231231231231231231231231231... >>> w.finite_differences(mod=Integer(2)) word: 1101101101101101101101101101101101101101...