# 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)

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)
True

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.

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()

class sage.combinat.words.words.FiniteWords_over_OrderedAlphabet(alphabet)

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)
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)

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)
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, *keys, **opts)

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)

EXAMPLES:

sage: from sage.combinat.words.words import Words_n
sage: w = Words_n(3)
True

class sage.combinat.words.words.Words_over_Alphabet(alphabet)

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])
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)

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)
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 or letter1 > letter2 respectively.

INPUT:

• letter1 - a letter in the alphabet
• letter2 - 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 $$(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 is self.
• min_length - (default: 1) nonnegative integer. If arg is not specified, then iterate through all the morphisms where the length of the images of each letter in the alphabet is at least min_length. This is ignored if arg 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): it.next()
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): it.next()
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->, 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->
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->, b->aa
WordMorphism: a->, b->ab
WordMorphism: a->, b->ba
WordMorphism: a->, b->bb

sage: for m in W.iter_morphisms( (2, 4) ): m
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
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


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): it.next()
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()


#### Previous topic

A collection of constructors of common words

#### Next topic

Shuffle product of words