Word classes¶

AUTHORS:

Arnaud Bergeron
Amy Glen
Sébastien Labbé
Franco Saliola

class sage.combinat.words.word.AbstractFiniteWord¶: Bases: sage.combinat.words.word.DeprecatedWordClass, sage.combinat.words.word.FiniteWord_list

class sage.combinat.words.word.AbstractInfiniteWord¶: Bases: sage.combinat.words.word.DeprecatedWordClass, sage.combinat.words.infinite_word.InfiniteWord_class

class sage.combinat.words.word.AbstractWord¶: Bases: sage.combinat.words.word.DeprecatedWordClass, sage.combinat.words.word.FiniteWord_list

class sage.combinat.words.word.DeprecatedWordClass¶: Bases: sage.structure.sage_object.SageObject

class sage.combinat.words.word.FiniteWord_callable(parent, callable, length=None)¶

Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable, sage.combinat.words.finite_word.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

TESTS:

sage: w = Word(lambda n:n, length=10, caching=False)
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable'>
sage: z = loads(dumps(w))
sage: w == z
True
sage: type(z)
<class 'sage.combinat.words.word.FiniteWord_callable'>

class sage.combinat.words.word.FiniteWord_callable_with_caching(parent, callable, length=None)¶

Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable_with_caching, sage.combinat.words.finite_word.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

TESTS:

sage: w = Word(lambda n:n, length=10)
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>
sage: z = loads(dumps(w))
sage: w == z
True
sage: type(z)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>

Pickle also works for concatenation of words:

sage: w = Word(range(10)) * Word('abcdef')
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>
sage: z = loads(dumps(w))
sage: w == z
True
sage: type(z)
<class 'sage.combinat.words.word.FiniteWord_list'>

Pickle also works for power of words:

sage: w = Word(range(10)) ^ 2
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_callable_with_caching'>
sage: z = loads(dumps(w))
sage: w == z
True
sage: type(z)
<class 'sage.combinat.words.word.FiniteWord_list'>

class sage.combinat.words.word.FiniteWord_iter(parent, iter, length=None)¶

Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter, sage.combinat.words.finite_word.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

TESTS:

sage: w = Word(iter(range(10)), caching=False)
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_iter'>
sage: z = loads(dumps(w))
sage: w == z
True
sage: type(z)
<class 'sage.combinat.words.word.FiniteWord_list'>

class sage.combinat.words.word.FiniteWord_iter_with_caching(parent, iter, length=None)¶

Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter_with_caching, sage.combinat.words.finite_word.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

TESTS:

sage: w = Word(iter(range(10)))
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_iter_with_caching'>
sage: z = loads(dumps(w))
sage: w == z
True
sage: type(z)
<class 'sage.combinat.words.word.FiniteWord_list'>

class sage.combinat.words.word.FiniteWord_list¶

Bases: sage.combinat.words.word_datatypes.WordDatatype_list, sage.combinat.words.finite_word.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...

TESTS:

sage: w = Word([0,1,1,0])
sage: w == loads(dumps(w))
True

class sage.combinat.words.word.FiniteWord_over_Alphabet¶: Bases: sage.combinat.words.word.DeprecatedWordClass, sage.combinat.words.word.FiniteWord_list

class sage.combinat.words.word.FiniteWord_over_OrderedAlphabet¶: Bases: sage.combinat.words.word.DeprecatedWordClass, sage.combinat.words.word.FiniteWord_list

class sage.combinat.words.word.FiniteWord_str¶

Bases: sage.combinat.words.word_datatypes.WordDatatype_str, sage.combinat.words.finite_word.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

TESTS:

sage: w = Word('abba')
sage: w == loads(dumps(w))
True

class sage.combinat.words.word.FiniteWord_tuple¶

Bases: sage.combinat.words.word_datatypes.WordDatatype_tuple, sage.combinat.words.finite_word.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

TESTS:

sage: w = Word((0,1,1,0))
sage: w == loads(dumps(w))
True

class sage.combinat.words.word.InfiniteWord_callable(parent, callable, length=None)¶

Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable, sage.combinat.words.infinite_word.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...

TESTS:

sage: w = Word(lambda n:n, caching=False)
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable'>
sage: z = loads(dumps(w))
sage: z
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: type(z)
<class 'sage.combinat.words.word.InfiniteWord_callable'>

class sage.combinat.words.word.InfiniteWord_callable_with_caching(parent, callable, length=None)¶

Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_callable_with_caching, sage.combinat.words.infinite_word.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

TESTS:

sage: w = Word(lambda n:n)
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_callable_with_caching'>
sage: z = loads(dumps(w))
sage: z
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: type(z)
<class 'sage.combinat.words.word.InfiniteWord_callable_with_caching'>

class sage.combinat.words.word.InfiniteWord_iter(parent, iter, length=None)¶

Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter, sage.combinat.words.infinite_word.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

TESTS:

sage: from itertools import count
sage: w = Word(count(), caching=False)
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_iter'>

Pickle is not supported for infinite word defined by an iterator:

sage: dumps(w)
...
PicklingError: Can't pickle <type 'generator'>: attribute lookup __builtin__.generator failed

class sage.combinat.words.word.InfiniteWord_iter_with_caching(parent, iter, length=None)¶

Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter_with_caching, sage.combinat.words.infinite_word.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

TESTS:

sage: from itertools import count
sage: w = Word(count())
sage: type(w)
<class 'sage.combinat.words.word.InfiniteWord_iter_with_caching'>

Pickle is not supported for infinite word defined by an iterator:

sage: dumps(w)
...
PicklingError: Can't pickle <type 'generator'>: attribute lookup __builtin__.generator failed

class sage.combinat.words.word.InfiniteWord_over_Alphabet¶: Bases: sage.combinat.words.word.DeprecatedWordClass, sage.combinat.words.infinite_word.InfiniteWord_class

class sage.combinat.words.word.InfiniteWord_over_OrderedAlphabet¶: Bases: sage.combinat.words.word.DeprecatedWordClass, sage.combinat.words.infinite_word.InfiniteWord_class

sage.combinat.words.word.Word(data=None, alphabet=None, length=None, datatype=None, caching=True)¶

Construct a word.

INPUT:

data - (default: None) list, string, tuple, iterator, None (shorthand for []), or a callable defined on [0,1,...,length].
alphabet - any argument accepted by Words
length - (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 know know the length.
datatype - (default: None) None, “list”, “str”, “tuple”, “iter”, “callable”. If None, then the function tries to guess this from the data.
caching - (default: True) True or False. Whether to keep a cache of the letters computed by an iterator or callable.

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:

Word with string:

sage: 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

Word with list:

sage: Word([0,1,1,0,1,0,0,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

Word with tuple:

sage: Word((0,1,1,0,1,0,0,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

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

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

Word over a string with a parent:

sage: w = Word("abbabaab", alphabet="abc"); w
word: abbabaab
sage: w.parent()
Words over Ordered Alphabet ['a', 'b', 'c']

The default parent is the combinatorial class of all words:

sage: w = Word("abbabaab"); w
word: abbabaab
sage: w.parent()
Words

TESTS:

sage: Word(5)
...
ValueError: Cannot guess a datatype from data (=5); please specify one

sage: w  = Word('abc')
sage: w is Word(w)
True
sage: w is Word(w, alphabet='abc')
False

class sage.combinat.words.word.Word_iter(parent, iter, length=None)¶

Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter, sage.combinat.words.abstract_word.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...

TESTS:

sage: w = Word(iter('abcd'*100), length='unknown', caching=False)
sage: type(w)
<class 'sage.combinat.words.word.Word_iter'>
sage: w
word: abcdabcdabcdabcdabcdabcdabcdabcdabcdabcd...

Pickle is not supported for word of unknown length defined by an iterator:

sage: dumps(w)
...
PicklingError: Can't pickle <type 'generator'>: attribute lookup __builtin__.generator failed

class sage.combinat.words.word.Word_iter_with_caching(parent, iter, length=None)¶

Bases: sage.combinat.words.word_infinite_datatypes.WordDatatype_iter_with_caching, sage.combinat.words.abstract_word.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...

TESTS:

sage: w = Word(iter('abcd'*100), length='unknown')
sage: type(w)
<class 'sage.combinat.words.word.Word_iter_with_caching'>
sage: w
word: abcdabcdabcdabcdabcdabcdabcdabcdabcdabcd...

Pickle is not supported for word of unknown length defined by an iterator:

sage: dumps(w)
...
PicklingError: Can't pickle <type 'generator'>: attribute lookup __builtin__.generator failed

class sage.combinat.words.word.Word_over_Alphabet¶: Bases: sage.combinat.words.word.DeprecatedWordClass, sage.combinat.words.word.FiniteWord_list

class sage.combinat.words.word.Word_over_OrderedAlphabet¶: Bases: sage.combinat.words.word.DeprecatedWordClass, sage.combinat.words.word.FiniteWord_list

sage.combinat.words.word.is_FiniteWord(obj)¶

Returns True if obj is a finite word, and False otherwise.

EXAMPLES:

sage: from sage.combinat.words.word import is_FiniteWord
sage: is_FiniteWord(33)
doctest:1: DeprecationWarning: is_Word is deprecated, use isinstance(your_object, Word_all) instead!
False
sage: is_FiniteWord(Word('baab'))
True

sage.combinat.words.word.is_Word(obj)¶

Returns True if obj is a word, and False otherwise.

EXAMPLES:

sage: from sage.combinat.words.word import is_Word
sage: is_Word(33)
doctest:1: DeprecationWarning: is_Word is deprecated, use isinstance(your_object, Word_all) instead!
False
sage: is_Word(Word('abba'))
True

Word classes¶

Previous topic

Next topic

This Page

Navigation

Word classes¶

Previous topic

Next topic

This Page

Quick search

Navigation