Set of words#
To define a new class of words, please refer to the documentation file: sage/combinat/words/notes/word_inheritance_howto.rst
AUTHORS:
Franco Saliola (2008-12-17): merged into sage
Sebastien Labbe (2008-12-17): merged into sage
Arnaud Bergeron (2008-12-17): merged into sage
Sebastien Labbe (2009-07-21): Improved morphism iterator (github issue #6571).
Vincent Delecroix (2015): classes simplifications (github issue #19619)
EXAMPLES:
sage: Words()
Finite and infinite words over Set of Python objects of class 'object'
sage: Words(4)
Finite and infinite words over {1, 2, 3, 4}
sage: Words(4,5)
Words of length 5 over {1, 2, 3, 4}
sage: FiniteWords('ab')
Finite words over {'a', 'b'}
sage: InfiniteWords('natural numbers')
Infinite words over Non negative integers
- class sage.combinat.words.words.AbstractLanguage(alphabet=None, category=None)#
Bases:
Parent
Abstract base class
This is not to be used by any means. This class gather previous features of set of words (prior to github issue #19619). In the future that class might simply disappear or become a common base class for all languages. In the latter case, its name would possibly change to
Language
.- alphabet()#
EXAMPLES:
sage: Words(NN).alphabet() Non negative integer semiring sage: InfiniteWords([1,2,3]).alphabet() {1, 2, 3} sage: InfiniteWords('ab').alphabet() {'a', 'b'} sage: FiniteWords([1,2,3]).alphabet() {1, 2, 3} sage: FiniteWords().alphabet() Set of Python objects of class 'object'
- identity_morphism()#
Returns the identity morphism from self to itself.
EXAMPLES:
sage: W = Words('ab') sage: W.identity_morphism() WordMorphism: a->a, b->b
sage: W = Words(range(3)) sage: W.identity_morphism() WordMorphism: 0->0, 1->1, 2->2
There is no support yet for infinite alphabet:
sage: W = Words(alphabet=Alphabet(name='NN')) sage: W Finite and infinite words over Non negative integers sage: W.identity_morphism() Traceback (most recent call last): ... NotImplementedError: size of alphabet must be finite
- class sage.combinat.words.words.FiniteOrInfiniteWords(alphabet)#
Bases:
AbstractLanguage
INPUT:
alphabet
– the underlying alphabet
- cardinality()#
Return the cardinality of this set of words.
EXAMPLES:
sage: Words('abcd').cardinality() +Infinity sage: Words('a').cardinality() +Infinity sage: Words('').cardinality() 1
- factors()#
Return the set of finite words.
EXAMPLES:
sage: Words('ab').finite_words() Finite words over {'a', 'b'}
- finite_words()#
Return the set of finite words.
EXAMPLES:
sage: Words('ab').finite_words() Finite words over {'a', 'b'}
- infinite_words()#
Return the set of infinite words.
EXAMPLES:
sage: Words('ab').infinite_words() Infinite words over {'a', 'b'}
- iterate_by_length(length)#
Return an iterator over the words of given length.
EXAMPLES:
sage: [w.string_rep() for w in Words('ab').iterate_by_length(3)] ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']
- shift()#
Return the set of infinite words.
EXAMPLES:
sage: Words('ab').infinite_words() Infinite words over {'a', 'b'}
- class sage.combinat.words.words.FiniteWords(alphabet=None, category=None)#
Bases:
AbstractLanguage
The set of finite words over a fixed alphabet.
EXAMPLES:
sage: W = FiniteWords('ab') sage: W Finite words over {'a', 'b'}
- cardinality()#
Return the cardinality of this set.
EXAMPLES:
sage: FiniteWords('').cardinality() 1 sage: FiniteWords('a').cardinality() +Infinity
- factors()#
Return itself.
EXAMPLES:
sage: FiniteWords('ab').factors() Finite words over {'a', 'b'}
- iter_morphisms(arg=None, codomain=None, min_length=1)#
Iterate over all morphisms with domain
self
and the given codomain.INPUT:
arg
- (optional, default:None
) It can be one of the following:None
- then the method iterates through all morphisms.tuple \((a, b)\) of two integers - It specifies the range
range(a, b)
of values to consider for the sum of the length of the image of each letter in the alphabet.list of nonnegative integers - The length of the list must be equal to the size of the alphabet, and the i-th integer of
arg
determines the length of the word mapped to by the i-th letter of the (ordered) alphabet.
codomain
- (default:None
) a combinatorial class of words. By default,codomain
isself
.min_length
- (default: 1) nonnegative integer. Ifarg
is not specified, then iterate through all the morphisms where the length of the images of each letter in the alphabet is at leastmin_length
. This is ignored ifarg
is a list.
OUTPUT:
iterator
EXAMPLES:
Iterator over all non-erasing morphisms:
sage: W = FiniteWords('ab') sage: it = W.iter_morphisms() sage: for _ in range(7): next(it) WordMorphism: a->a, b->a WordMorphism: a->a, b->b WordMorphism: a->b, b->a WordMorphism: a->b, b->b WordMorphism: a->aa, b->a WordMorphism: a->aa, b->b WordMorphism: a->ab, b->a
Iterator over all morphisms including erasing morphisms:
sage: W = FiniteWords('ab') sage: it = W.iter_morphisms(min_length=0) sage: for _ in range(7): next(it) WordMorphism: a->, b-> WordMorphism: a->a, b-> WordMorphism: a->b, b-> WordMorphism: a->, b->a WordMorphism: a->, b->b WordMorphism: a->aa, b-> WordMorphism: a->ab, b->
Iterator over morphisms where the sum of the lengths of the images of the letters is in a specific range:
sage: for m in W.iter_morphisms((0, 3), min_length=0): m WordMorphism: a->aa, b-> WordMorphism: a->ab, b-> WordMorphism: a->ba, b-> WordMorphism: a->bb, b-> WordMorphism: a->a, b->a WordMorphism: a->a, b->b WordMorphism: a->b, b->a WordMorphism: a->b, b->b WordMorphism: a->a, b-> WordMorphism: a->b, b-> WordMorphism: a->, b->aa WordMorphism: a->, b->ab WordMorphism: a->, b->ba WordMorphism: a->, b->bb WordMorphism: a->, b->a WordMorphism: a->, b->b WordMorphism: a->, b->
sage: for m in W.iter_morphisms( (2, 4) ): m WordMorphism: a->aa, b->a WordMorphism: a->aa, b->b WordMorphism: a->ab, b->a WordMorphism: a->ab, b->b WordMorphism: a->ba, b->a WordMorphism: a->ba, b->b WordMorphism: a->bb, b->a WordMorphism: a->bb, b->b WordMorphism: a->a, b->aa WordMorphism: a->a, b->ab WordMorphism: a->a, b->ba WordMorphism: a->a, b->bb WordMorphism: a->b, b->aa WordMorphism: a->b, b->ab WordMorphism: a->b, b->ba WordMorphism: a->b, b->bb WordMorphism: a->a, b->a WordMorphism: a->a, b->b WordMorphism: a->b, b->a WordMorphism: a->b, b->b
Iterator over morphisms with specific image lengths:
sage: for m in W.iter_morphisms([0, 0]): m WordMorphism: a->, b-> sage: for m in W.iter_morphisms([0, 1]): m WordMorphism: a->, b->a WordMorphism: a->, b->b sage: for m in W.iter_morphisms([2, 1]): m WordMorphism: a->aa, b->a WordMorphism: a->aa, b->b WordMorphism: a->ab, b->a WordMorphism: a->ab, b->b WordMorphism: a->ba, b->a WordMorphism: a->ba, b->b WordMorphism: a->bb, b->a WordMorphism: a->bb, b->b sage: for m in W.iter_morphisms([2, 2]): m WordMorphism: a->aa, b->aa WordMorphism: a->aa, b->ab WordMorphism: a->aa, b->ba WordMorphism: a->aa, b->bb WordMorphism: a->ab, b->aa WordMorphism: a->ab, b->ab WordMorphism: a->ab, b->ba WordMorphism: a->ab, b->bb WordMorphism: a->ba, b->aa WordMorphism: a->ba, b->ab WordMorphism: a->ba, b->ba WordMorphism: a->ba, b->bb WordMorphism: a->bb, b->aa WordMorphism: a->bb, b->ab WordMorphism: a->bb, b->ba WordMorphism: a->bb, b->bb
The codomain may be specified as well:
sage: Y = FiniteWords('xyz') sage: for m in W.iter_morphisms([0, 2], codomain=Y): m WordMorphism: a->, b->xx WordMorphism: a->, b->xy WordMorphism: a->, b->xz WordMorphism: a->, b->yx WordMorphism: a->, b->yy WordMorphism: a->, b->yz WordMorphism: a->, b->zx WordMorphism: a->, b->zy WordMorphism: a->, b->zz sage: for m in Y.iter_morphisms([0,2,1], codomain=W): m WordMorphism: x->, y->aa, z->a WordMorphism: x->, y->aa, z->b WordMorphism: x->, y->ab, z->a WordMorphism: x->, y->ab, z->b WordMorphism: x->, y->ba, z->a WordMorphism: x->, y->ba, z->b WordMorphism: x->, y->bb, z->a WordMorphism: x->, y->bb, z->b sage: it = W.iter_morphisms(codomain=Y) sage: for _ in range(10): next(it) WordMorphism: a->x, b->x WordMorphism: a->x, b->y WordMorphism: a->x, b->z WordMorphism: a->y, b->x WordMorphism: a->y, b->y WordMorphism: a->y, b->z WordMorphism: a->z, b->x WordMorphism: a->z, b->y WordMorphism: a->z, b->z WordMorphism: a->xx, b->x
- iterate_by_length(l=1)#
Returns an iterator over all the words of self of length l.
INPUT:
l
- integer (default: 1), the length of the desired words
EXAMPLES:
sage: W = FiniteWords('ab') sage: list(W.iterate_by_length(1)) [word: a, word: b] sage: list(W.iterate_by_length(2)) [word: aa, word: ab, word: ba, word: bb] sage: list(W.iterate_by_length(3)) [word: aaa, word: aab, word: aba, word: abb, word: baa, word: bab, word: bba, word: bbb] sage: list(W.iterate_by_length('a')) Traceback (most recent call last): ... TypeError: the parameter l (='a') must be an integer
- random_element(length=None, *args, **kwds)#
Returns a random finite word on the given alphabet.
INPUT:
length
– (optional) the length of the word. If not set, will use a uniformly random number between 0 and 10.all other argument are transmitted to the random generator of the alphabet
EXAMPLES:
sage: W = FiniteWords(5) sage: W.random_element() # random word: 5114325445423521544531411434451152142155... sage: W = FiniteWords(ZZ) sage: W.random_element() # random word: 5,-1,-1,-1,0,0,0,0,-3,-11 sage: W.random_element(length=4, x=0, y=4) # random word: 1003
- shift()#
Return the set of infinite words on the same alphabet.
EXAMPLES:
sage: FiniteWords('ab').shift() Infinite words over {'a', 'b'}
- class sage.combinat.words.words.InfiniteWords(alphabet=None, category=None)#
Bases:
AbstractLanguage
- cardinality()#
Return the cardinality of this set
EXAMPLES:
sage: InfiniteWords('ab').cardinality() +Infinity sage: InfiniteWords('a').cardinality() 1 sage: InfiniteWords('').cardinality() 0
- factors()#
Return the set of finite words on the same alphabet.
EXAMPLES:
sage: InfiniteWords('ab').factors() Finite words over {'a', 'b'}
- random_element(*args, **kwds)#
Return a random infinite word.
EXAMPLES:
sage: W = InfiniteWords('ab') sage: W.random_element() # random word: abbbabbaabbbabbabbaabaabbabbbbbbbbaabbbb... sage: W = InfiniteWords(ZZ) sage: W.random_element(x=2,y=4) # random word: 3333223322232233333223323223222233233233...
- shift()#
Return itself.
EXAMPLES:
sage: InfiniteWords('ab').shift() Infinite words over {'a', 'b'}
- sage.combinat.words.words.Words(alphabet=None, length=None, finite=True, infinite=True)#
Returns the combinatorial class of words of length k over an alphabet.
EXAMPLES:
sage: Words() Finite and infinite words over Set of Python objects of class 'object' sage: Words(length=7) Words of length 7 over Set of Python objects of class 'object' sage: Words(5) Finite and infinite words over {1, 2, 3, 4, 5} sage: Words(5, 3) Words of length 3 over {1, 2, 3, 4, 5} sage: Words(5, infinite=False) Finite words over {1, 2, 3, 4, 5} sage: Words(5, finite=False) Infinite words over {1, 2, 3, 4, 5} sage: Words('ab') Finite and infinite words over {'a', 'b'} sage: Words('ab', 2) Words of length 2 over {'a', 'b'} sage: Words('ab', infinite=False) Finite words over {'a', 'b'} sage: Words('ab', finite=False) Infinite words over {'a', 'b'} sage: Words('positive integers', finite=False) Infinite words over Positive integers sage: Words('natural numbers') Finite and infinite words over Non negative integers
- class sage.combinat.words.words.Words_n(words, n)#
Bases:
Parent
The set of words of fixed length on a given alphabet.
- alphabet()#
Return the underlying alphabet.
EXAMPLES:
sage: Words([0,1], 4).alphabet() {0, 1}
- cardinality()#
Returns the number of words of length \(n\) from alphabet.
EXAMPLES:
sage: Words(['a','b','c'], 4).cardinality() 81 sage: Words(3, 4).cardinality() 81 sage: Words(0,0).cardinality() 1 sage: Words(5,0).cardinality() 1 sage: Words(['a','b','c'],0).cardinality() 1 sage: Words(0,1).cardinality() 0 sage: Words(5,1).cardinality() 5 sage: Words(['a','b','c'],1).cardinality() 3 sage: Words(7,13).cardinality() 96889010407 sage: Words(['a','b','c','d','e','f','g'],13).cardinality() 96889010407
- iterate_by_length(length)#
All words in this class are of the same length, so use iterator instead.
- list()#
Returns a list of all the words contained in self.
EXAMPLES:
sage: Words(0,0).list() [word: ] sage: Words(5,0).list() [word: ] sage: Words(['a','b','c'],0).list() [word: ] sage: Words(5,1).list() [word: 1, word: 2, word: 3, word: 4, word: 5] sage: Words(['a','b','c'],2).list() [word: aa, word: ab, word: ac, word: ba, word: bb, word: bc, word: ca, word: cb, word: cc]
- random_element(*args, **kwds)#
Return a random word in this set.
EXAMPLES:
sage: W = Words('ab', 4) sage: W.random_element() # random word: bbab sage: W.random_element() in W True sage: W = Words(ZZ, 5) sage: W.random_element() # random word: 1,2,2,-1,12 sage: W.random_element() in W True