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 (trac ticket #6571).

• Vincent Delecroix (2015): classes simplifications (trac ticket #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: sage.structure.parent.Parent

Abstract base class

This is not to be used by any means. This class gather previous features of set of words (prior to trac ticket #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: sage.combinat.words.words.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: sage.combinat.words.words.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 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 = 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: sage.combinat.words.words.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: sage.structure.parent.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