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

EXAMPLES:

sage: Words()
Words
sage: Words(5)
Words over Ordered Alphabet [1, 2, 3, 4, 5]
sage: Words('ab')
Words over Ordered Alphabet ['a', 'b']
sage: Words('natural numbers')
Words over Ordered Alphabet of Natural Numbers
class sage.combinat.words.words.FiniteWords_length_k_over_OrderedAlphabet(alphabet, length)
__contains__(x)

EXAMPLES:

sage: from sage.combinat.words.words import FiniteWords_length_k_over_OrderedAlphabet
sage: A = sage.combinat.words.alphabet.OrderedAlphabet([0,1])
sage: W = FiniteWords_length_k_over_OrderedAlphabet(A, 3)
sage: [1,2,3] in W
False
sage: [1,2] in W
False
sage: Words([0,1])([1,0,1]) in W
True
sage: Words([1,0])([1,0,1]) in W
False
sage: W([1,0,1]) in W
True
sage: Word([2,0]) in W
False
__init__(alphabet, length)

TESTS:

sage: from sage.combinat.words.words import FiniteWords_length_k_over_OrderedAlphabet
sage: A = sage.combinat.words.alphabet.OrderedAlphabet([0,1])
sage: W = FiniteWords_length_k_over_OrderedAlphabet(A, 3)
sage: W == loads(dumps(W))
True
__iter__()

Returns an iterator for all of the words of length k from self.alphabet(). The iterator outputs the words in lexicographic order, with respect to the ordering of the alphabet.

TESTS:

sage: [w for w in Words(['a', 'b'], 2)]
[word: aa, word: ab, word: ba, word: bb]
sage: [w for w in Words(['b', 'a'], 2)] 
[word: bb, word: ba, word: ab, word: aa]
sage: [w for w in Words(['a', 'b'], 0)]
[word: ]
sage: [w for w in Words([], 3)]
[]
__repr__()

TESTS:

sage: from sage.combinat.words.words import FiniteWords_length_k_over_OrderedAlphabet
sage: A = sage.combinat.words.alphabet.OrderedAlphabet([1,0])
sage: FiniteWords_length_k_over_OrderedAlphabet(A,3).__repr__()
'Finite Words of length 3 over Ordered Alphabet [1, 0]'
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]
class sage.combinat.words.words.FiniteWords_over_OrderedAlphabet(alphabet)
__init__(alphabet)

EXAMPLES:

sage: from sage.combinat.words.words import FiniteWords_over_OrderedAlphabet
sage: from sage.combinat.words.alphabet import OrderedAlphabet
sage: A = OrderedAlphabet("abc")
sage: W = FiniteWords_over_OrderedAlphabet(A)
sage: W == loads(dumps(W))
True
__repr__()

Returns a string representation of self.

EXAMPLES:

sage: Words('ab', infinite=False).__repr__()
"Finite Words over Ordered Alphabet ['a', 'b']"
class sage.combinat.words.words.InfiniteWords_over_OrderedAlphabet(alphabet)
__init__(alphabet)

EXAMPLES:

sage: from sage.combinat.words.words import InfiniteWords_over_OrderedAlphabet
sage: from sage.combinat.words.alphabet import OrderedAlphabet
sage: A = OrderedAlphabet("abc")
sage: W = InfiniteWords_over_OrderedAlphabet(A)
sage: W == loads(dumps(W))
True
__repr__()

Returns a string representation of self.

EXAMPLES:

sage: Words('ab', infinite=False).__repr__()
"Finite Words over Ordered Alphabet ['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 ordered alphabet.

EXAMPLES:

sage: Words()
Words
sage: Words(length=7)
Finite Words of length 7
sage: Words(5)
Words over Ordered Alphabet [1, 2, 3, 4, 5]
sage: Words(5, 3)
Finite Words of length 3 over Ordered Alphabet [1, 2, 3, 4, 5]
sage: Words(5, infinite=False)
Finite Words over Ordered Alphabet [1, 2, 3, 4, 5]
sage: Words(5, finite=False)
Infinite Words over Ordered Alphabet [1, 2, 3, 4, 5]
sage: Words('ab')
Words over Ordered Alphabet ['a', 'b']
sage: Words('ab', 2)
Finite Words of length 2 over Ordered Alphabet ['a', 'b']
sage: Words('ab', infinite=False)
Finite Words over Ordered Alphabet ['a', 'b']
sage: Words('ab', finite=False)
Infinite Words over Ordered Alphabet ['a', 'b']
sage: Words('positive integers', finite=False)
Infinite Words over Ordered Alphabet of Positive Integers
sage: Words('natural numbers')
Words over Ordered Alphabet of Natural Numbers
class sage.combinat.words.words.Words_all

TESTS:

sage: from sage.combinat.words.words import Words_all
sage: list(Words_all())
...
NotImplementedError
sage: Words_all().list()
...
NotImplementedError: infinite list
sage: Words_all().cardinality()
+Infinity
__call__(data=None, length=None, datatype=None, **kwds)

Construct a new word object with parent self.

NOTE:

We only check that the first 40 letters of the word are actually in the alphabet. This is a quick check implemented to test for small programming errors. Since we also support infinite words, we cannot really implement a more accurate check.

EXAMPLES:

sage: from itertools import count
sage: Words()(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: Words(range(10))(count())
...
ValueError: 10 not in alphabet!
sage: Words()("abba")
word: abba
sage: Words("ab")("abba")
word: abba
sage: Words("ab")("abca")
...
ValueError: c not in alphabet!
__contains__(x)

Returns True if x is contained in self.

EXAMPLES:

sage: from sage.combinat.words.words import Words_all
sage: 2 in Words_all()
False
sage: [1,2] in Words_all()
False
sage: Words('ab')('abba') in Words_all()
True
__repr__()

EXAMPLES:

sage: from sage.combinat.words.words import Words_all
sage: Words_all().__repr__()
'Words'
_check(w, length=40)

Check that the first length elements are actually in the alphabet.

NOTE:

EXAMPLES:

sage: from sage.combinat.words.words import Words_over_Alphabet
sage: W = Words_over_Alphabet(['a','b','c'])
sage: W._check('abcabc') is None
True
sage: W._check('abcabcd')
...
ValueError: d not in alphabet!
sage: W._check('abcabc'*10+'z') is None
True
sage: W._check('abcabc'*10+'z', length=80)
...
ValueError: z not in alphabet!
class _python_object_alphabet

The “ordered” alphabet of all Python objects.

__contains__(x)

Returns always True.

EXAMPLES:

sage: W = Words()
sage: A = W._python_object_alphabet()
sage: 'a' in A
True
sage: 5 in A
True
sage: 'abcdef' in A
True
sage: [4,5] in A
True
__repr__()

EXAMPLES:

sage: W = Words()
sage: A = W._python_object_alphabet()
sage: A
Python objects
__weakref__
list of weak references to the object (if defined)
Words_all.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.words import OrderedAlphabet
sage: W = Words_over_Alphabet(OrderedAlphabet('ab'))
sage: W.alphabet()
Ordered Alphabet ['a', 'b']
Words_all.cmp_letters()

cmp(x, y) -> integer

Return negative if x<y, zero if x==y, positive if x>y.

Words_all.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
Words_all.size_of_alphabet()

Returns the size of the alphabet.

EXAMPLES:

sage: Words().size_of_alphabet()
+Infinity
class sage.combinat.words.words.Words_n(n)
__contains__(x)

EXAMPLES:

sage: from sage.combinat.words.words import Words_n
sage: 2 in Words_n(3)
False
sage: [1,'a',3] in Words_n(3)
False
sage: [1,2] in Words_n(3)
False
sage: "abc" in Words_n(3)
False
sage: Words("abc")("ababc") in Words_n(3)
False
sage: Words([0,1])([1,0,1]) in Words_n(3)
True
__init__(n)

EXAMPLES:

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

EXAMPLES:

sage: from sage.combinat.words.words import Words_n
sage: Words_n(3).__repr__()
'Finite Words of length 3'
class sage.combinat.words.words.Words_over_Alphabet(alphabet)
__contains__(x)

Tests whether self contains x.

OUTPUT:
This method returns True if x is a word of the appropriate length and the alphabets of the parents match. Returns False otherwise.

EXAMPLES:

sage: from sage.combinat.words.words import Words_over_Alphabet
sage: from sage.combinat.words.words import OrderedAlphabet
sage: A = OrderedAlphabet('ab')
sage: Words(A)('abba') in Words_over_Alphabet(A)
True
sage: Words(A)('aa') in Words_over_Alphabet(A)
True
sage: Words('a')('aa') in Words_over_Alphabet(A)
False
sage: 2 in Words_over_Alphabet([1,2,3])
False
sage: [2] in Words_over_Alphabet([1,2,3])
False
sage: [1, 'a'] in Words_over_Alphabet([1,2,3])
False
__ge__(other)

Returns True if self is a superset of other and False otherwise.

TESTS:

sage: Words('ab') >= Words('ab')
True
sage: Words('ab') >= Words('abc')
False
sage: Words('abc') >= Words('ab')
True
__gt__(other)

Returns True if self is a proper superset of other and False otherwise.

TESTS:

sage: Words('ab') > Words('ab')
False
sage: Words('ab') > Words('abc')
False
sage: Words('abc') > Words('ab')
True
__init__(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])
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
__le__(other)

Returns True if self is a subset of other and False otherwise.

TESTS:

sage: Words('ab') <= Words('ab')
True
sage: Words('ab') <= Words('abc')
True
sage: Words('abc') <= Words('ab')
False
__lt__(other)

Returns whether self is a proper subset of other.

TESTS:

sage: Words('ab') < Words('ab')
False
sage: Words('ab') < Words('abc')
True
sage: Words('abc') < Words('ab')
False
__repr__()

EXAMPLES:

sage: from sage.combinat.words.words import Words_over_Alphabet
sage: Words_over_Alphabet([1,2,3]).__repr__()
'Words over [1, 2, 3]'
size_of_alphabet()

Returns the size of the alphabet.

EXAMPLES:

sage: Words('abcdef').size_of_alphabet()
6
sage: Words('').size_of_alphabet()
0
class sage.combinat.words.words.Words_over_OrderedAlphabet(alphabet)
__init__(alphabet)

EXAMPLES:

sage: from sage.combinat.words.words import Words_over_OrderedAlphabet
sage: from sage.combinat.words.alphabet import OrderedAlphabet
sage: A = OrderedAlphabet("abc")
sage: W = Words_over_OrderedAlphabet(A)
sage: W == loads(dumps(W))
True
__iter__()

Returns an iterator over all the words of self.

The iterator outputs the words in lexicographic order, based on the order of the letters in the alphabet.

EXAMPLES:

sage: W = Words([4,5])
sage: for w in W:
...     if len(w)>3:
...         break
...     else:
...         print w
...
word:
word: 4
word: 5
word: 44
word: 45
word: 54
word: 55
word: 444
word: 445
word: 454
word: 455
word: 544
word: 545
word: 554
word: 555
sage: W = Words([5,4])
sage: for w in W:
...     if len(w)>3:
...         break
...     else:
...         print w
...
word:
word: 5
word: 4
word: 55
word: 54
word: 45
word: 44
word: 555
word: 554
word: 545
word: 544
word: 455
word: 454
word: 445
word: 444
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.words import OrderedAlphabet
sage: A = OrderedAlphabet('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(l, codomain=None)

Returns an iterator over all morphisms \varphi from self to codomain such that |\varphi| = l.

Let \varphi:\Sigma^*\rightarrow \Omega^* be a morphism. We denote by |\varphi| the function \Sigma\rightarrow\mathbb{N} defined by a\mapsto |\varphi(a)|.

INPUT:

  • l - list of k integers where k is the number of letters in the alphabet. The i-th element of l gives the length of the image of the i-th letter of the ordered alphabet.
  • codomain - (default : None) a combinatorial class of words. By default, the codomain is self.

OUTPUT:

iterator

EXAMPLES:

sage: W = Words('ab')                 
sage: map(str, W.iter_morphisms([2, 1]))
['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: map(str, W.iter_morphisms([2, 2]))
['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']
sage: map(str, W.iter_morphisms([0, 0]))
['WordMorphism: a->, b->']
sage: map(str, W.iter_morphisms([0, 1]))
['WordMorphism: a->, b->a', 'WordMorphism: a->, b->b']

You may specify the codomain as well:

sage: Y = Words('xyz')
sage: map(str, W.iter_morphisms([0,2], codomain=Y))
['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: map(str, Y.iter_morphisms([0,2,1], codomain=W))
['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']

TESTS:

sage: list(W.iter_morphisms([1,0]))
[Morphism from Words over Ordered Alphabet ['a', 'b'] to Words over Ordered Alphabet ['a', 'b'], Morphism from Words over Ordered Alphabet ['a', 'b'] to Words over Ordered Alphabet ['a', 'b']]
sage: list(W.iter_morphisms([0,0], codomain=Y))   
[Morphism from Words over Ordered Alphabet ['a', 'b'] to Words over Ordered Alphabet ['x', 'y', 'z']]
sage: list(W.iter_morphisms([0, 1, 2]))
...
TypeError: l (=[0, 1, 2]) must be a list of 2 integers
sage: list(W.iter_morphisms([0, 'a'])) 
...
TypeError: l (=[0, 'a']) must be a list of 2 integers
sage: list(W.iter_morphisms([0, 1], codomain='a')) 
...
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'))
...
TypeError: the parameter l (='a') must be an integer
sage.combinat.words.words.is_Words(obj)

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

EXAMPLES:

sage: from sage.combinat.words.words import is_Words
sage: is_Words(33)
doctest:1: DeprecationWarning: is_Words is deprecated, use isinstance(your_object, Words_all) instead!
False
sage: is_Words(Words('ab'))
True

Previous topic

A collection of constructors of common words

Next topic

Word utilities (DEPRECATED)

This Page