Combinatorial classes of words.¶
To define a new class of words, please refer to the documentation file: sage/combinat/words/notes/word_inheritance_howto.txt
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 (#6571).
EXAMPLES:
sage: Words()
Words
sage: Words(4)
Words over {1, 2, 3, 4}
sage: Words('ab')
Words over {'a', 'b'}
sage: Words('natural numbers')
Words over Non negative integers
-
class
sage.combinat.words.words.
FiniteWords_length_k_over_OrderedAlphabet
(alphabet, length)¶ Bases:
sage.combinat.words.words.FiniteWords_over_OrderedAlphabet
TESTS:
sage: from sage.combinat.words.words import FiniteWords_length_k_over_OrderedAlphabet sage: A = sage.combinat.words.alphabet.build_alphabet([0,1]) sage: W = FiniteWords_length_k_over_OrderedAlphabet(A, 3) sage: W == loads(dumps(W)) True
-
cardinality
()¶ Returns the number of words of length
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.
TESTS:
sage: W = Words(['a', 'b'], 2) sage: list(W.iterate_by_length(2)) [word: aa, word: ab, word: ba, word: bb] sage: list(W.iterate_by_length(1)) []
-
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
()¶ Returns a random word uniformly.
The word returned has infinite length, and is built by randomly picking a letter from the alphabet, one after the other.
EXAMPLE:
sage: W = Words(2,20) sage: W.random_element() # random word: 11212222211111221112 sage: W = Words(ZZ,20) sage: W.random_element() Traceback (most recent call last): ... ValueError: How can I pick a random word with an infinite aphabet?
TESTS:
sage: _ = Words(GF(5),4).random_element()
Check that trac ticket #18283 is fixed:
sage: w = Words('abc', 5).random_element() sage: w.length() 5
-
-
class
sage.combinat.words.words.
FiniteWords_over_OrderedAlphabet
(alphabet)¶ Bases:
sage.combinat.words.words.Words_over_OrderedAlphabet
EXAMPLES:
sage: from sage.combinat.words.words import FiniteWords_over_OrderedAlphabet sage: from sage.combinat.words.alphabet import build_alphabet sage: A = build_alphabet("abc") sage: W = FiniteWords_over_OrderedAlphabet(A) sage: W == loads(dumps(W)) True
-
random_element
()¶ Returns a random (infinite) word on the given alphabet.
EXAMPLE:
sage: W = Words(5, infinite=False) sage: W.random_element() Traceback (most recent call last): ... ValueError: What does it mean to pick a random finite word over a given alphabet?
-
-
class
sage.combinat.words.words.
InfiniteWords_over_OrderedAlphabet
(alphabet)¶ Bases:
sage.combinat.words.words.Words_over_OrderedAlphabet
EXAMPLES:
sage: from sage.combinat.words.words import InfiniteWords_over_OrderedAlphabet sage: from sage.combinat.words.alphabet import build_alphabet sage: A = build_alphabet("abc") sage: W = InfiniteWords_over_OrderedAlphabet(A) sage: W == loads(dumps(W)) True
-
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() Words sage: Words(length=7) Words of length 7 sage: Words(5) 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') 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') Words over Non negative integers
-
class
sage.combinat.words.words.
Words_all
(category=None)¶ Bases:
sage.combinat.combinat.InfiniteAbstractCombinatorialClass
TESTS:
sage: from sage.combinat.words.words import Words_all sage: list(Words_all()) Traceback (most recent call last): ... NotImplementedError sage: Words_all().list() Traceback (most recent call last): ... NotImplementedError: infinite list sage: Words_all().cardinality() +Infinity sage: isinstance(Words('ab'), Words_all) True sage: isinstance(33, Words_all) False
We would like the instance of this class to be unique:
sage: Words() is Words() # todo: not implemented True
Warning
The design of these classes is not particularly robust so extra care must be taken when extending this class in order to prevent unintended side-effects. This is particularly evident in the equality test
__eq__()
for words.-
alphabet
()¶ EXAMPLES:
sage: from sage.combinat.words.words import Words_over_Alphabet sage: W = Words_over_Alphabet([1,2,3]) sage: W.alphabet() [1, 2, 3] sage: from sage.combinat.words.alphabet import build_alphabet sage: W = Words_over_Alphabet(build_alphabet('ab')) sage: W.alphabet() {'a', 'b'} sage: w = Word('abaccefa') sage: w.parent().alphabet() Set of Python objects of type 'object' sage: Words('456').alphabet() {'4', '5', '6'}
-
has_letter
(letter)¶ Returns True if the alphabet of self contains the given letter.
INPUT:
letter
- a letter
EXAMPLES:
sage: W = Words() sage: W.has_letter('a') True sage: W.has_letter(1) True sage: W.has_letter({}) True sage: W.has_letter([]) True sage: W.has_letter(range(5)) True sage: W.has_letter(Permutation([])) True sage: from sage.combinat.words.words import Words_over_Alphabet sage: W = Words_over_Alphabet(['a','b','c']) sage: W.has_letter('a') True sage: W.has_letter('d') False sage: W.has_letter(8) False
-
size_of_alphabet
()¶ Returns the size of the alphabet.
EXAMPLES:
sage: Words().size_of_alphabet() +Infinity sage: Word('abaccefa').parent().size_of_alphabet() +Infinity
-
-
class
sage.combinat.words.words.
Words_n
(n)¶ Bases:
sage.combinat.words.words.Words_all
EXAMPLES:
sage: from sage.combinat.words.words import Words_n sage: W = Words_n(3) sage: W Words of length 3 sage: W == loads(dumps(W)) True
-
class
sage.combinat.words.words.
Words_over_Alphabet
(alphabet)¶ Bases:
sage.combinat.words.words.Words_all
Words over Alphabet.
INPUT:
alphabet
- assumed to be an instance of Alphabet, but no type checking is done here.
EXAMPLES:
sage: from sage.combinat.words.words import Words_over_Alphabet sage: W = Words_over_Alphabet([1,2,3]) sage: W == loads(dumps(W)) True
The input alphabet must be an instance of Alphabet:
sage: W = Words_over_Alphabet(Alphabet([1,2,3])) sage: W([1,2,2,3]) word: 1223
-
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 Words over Non negative integers sage: W.identity_morphism() Traceback (most recent call last): ... NotImplementedError: size of alphabet must be finite
-
size_of_alphabet
()¶ Returns the size of the alphabet.
EXAMPLES:
sage: Words('abcdef').size_of_alphabet() 6 sage: Words('').size_of_alphabet() 0 sage: Words('456').size_of_alphabet() 3
-
class
sage.combinat.words.words.
Words_over_OrderedAlphabet
(alphabet)¶ Bases:
sage.combinat.words.words.Words_over_Alphabet
EXAMPLES:
sage: from sage.combinat.words.words import Words_over_OrderedAlphabet sage: from sage.combinat.words.alphabet import build_alphabet sage: A = build_alphabet("abc") sage: W = Words_over_OrderedAlphabet(A) sage: W == loads(dumps(W)) True
TESTS:
Impossible to iterate over the uncountable set of all words on a given alphabet:
sage: Words(4)[1] Traceback (most recent call last): ... NotImplementedError
-
cmp_letters
(letter1, letter2)¶ Returns a negative number, zero or a positive number if
letter1
<letter2
,letter1
==letter2
orletter1
>letter2
respectively.INPUT:
letter1
- a letter in the alphabetletter2
- a letter in the alphabet
EXAMPLES:
sage: from sage.combinat.words.words import Words_over_OrderedAlphabet sage: from sage.combinat.words.alphabet import build_alphabet sage: A = build_alphabet('woa') sage: W = Words_over_OrderedAlphabet(A) sage: W.cmp_letters('w','a') -2 sage: W.cmp_letters('w','o') -1 sage: W.cmp_letters('w','w') 0
-
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
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 = Words('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 = Words('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 = Words('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
TESTS:
sage: list(W.iter_morphisms([1,0])) [WordMorphism: a->a, b->, WordMorphism: a->b, b->] sage: list(W.iter_morphisms([0,0], codomain=Y)) [WordMorphism: a->, b->] sage: list(W.iter_morphisms([0, 1, 2])) Traceback (most recent call last): ... TypeError: arg (=[0, 1, 2]) must be an iterable of 2 integers sage: list(W.iter_morphisms([0, 'a'])) Traceback (most recent call last): ... TypeError: arg (=[0, 'a']) must be an iterable of 2 integers sage: list(W.iter_morphisms([0, 1], codomain='a')) Traceback (most recent call last): ... TypeError: codomain (=a) must be an instance of Words_over_OrderedAlphabet
-
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 = Words('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
()¶ Returns a random (infinite) word on the given alphabet.
The word returned has infinite length, and is built by randomly picking a letter from the alphabet, one after the other.
EXAMPLE:
sage: W = Words(5) sage: W.random_element() # random word: 5114325445423521544531411434451152142155... sage: W = Words(ZZ) sage: W.random_element() Traceback (most recent call last): ... ValueError: How can I pick a random word with an infinite aphabet?
TESTS:
sage: _ = Words(GF(5)).random_element()
-