, optimal.The library combinat::words provides functions for counting, generating, and manipulating words.
Superdomain
Superdomain
Categories
Cat::CombinatorialClass, Cat::FacadeDomain(DOM_LIST)
Axioms
Details:
A word of length k over the alphabet A is a list of k elements of A. The alphabet A can be represented in MuPAD by a set (DOM_SET) or a list (DOM_LIST). A nonnegative integer n can be used as a shortcut for the alphabet [1,2,...,n]. The order between the letters is specified by the order of the operands in A.
Entries
|
"domtype" |
The MuPAD domain used to represent words: DOM_LIST |
isA – check if an object is a word
combinat::words::isA(word w, <alphabet A, size k>)
combinat::words::isA(word w, <nonnegative integer n, size k>)
Returns TRUE if w is a word. If the alphabet and/or the size are given, it also checks if w is of length k on the alphabet A or [1,2,...,n].
count – number of words
combinat::words::count(alphabet A, nonnegative integer k)
combinat::words::count(nonnegative integer n, nonnegative integer k)
Returns the number of words of length k on the alphabet A or [1,2,...,n].
list – list of words
combinat::words::list(alphabet A, nonnegative integer k)
combinat::words::list(nonnegative integer n, nonnegative integer k)
Returns the list of the words of length k on the alphabet A or [1,2,...,n].
generator – generator for words
combinat::words::generator(alphabet A, nonnegative integer k)
combinat::words::generator(nonnegative integer n, nonnegative integer k)
Returns a generator for the words of length k on the alphabet A or [1,2,...,n].
alphabet – alphabet of a word
combinat::words::alphabet(word w)
Returns the alphabet of th word w.
restriction – restriction of a word to a subset of its alphabet
combinat::words::restriction(word w, alphabet sset)
Returns the subword of the word w with alphabet sset.
length – length of a word
combinat::words::length(word w)
Returns the length of the word w.
alphabetToOrder – ordering function of an alphabet
combinat::words::alphabetToOrder(alphabet A)
Returns the ordering function of the alphabet A. Such a function takes two elements x and y of A and returns TRUE if x occurs before y in A.
standard – standard permutation of a word
combinat::words::standard(word w)
combinat::words::standard(word w, alphabet A)
combinat::words::standard(word w, ordering o)
Returns the standard permutation of the word w on the ordered alphabet A. It is defined as the permutation with exactly the same inversions than w (see combinat::permutations). By default, the letters are ordered using <. A custom ordering can be specified by providing an alphabet A, or an ordering function o that returns TRUE if its first argument is smaller than its second one.
Complexity: , optimal.
Evaluations of words
The evaluation of a word w encodes the number of occurrences of each letter of w.
In general, the evaluation may be represented as a table, the evaluation of [1,1,1,2,1,4,4] being the table(1=4, 2=1, 4=2), or as a sorted associative list [[1,4], [2,1], [4,2]].
When an ordered alphabet is specified, the evaluation can be represented as an integer vector c such that c[i] is the number of occurrences of the i-th letter of the alphabet in w. With the above word and the alphabet [2,1,4], we get the evaluation [1,4,2]. In the special case where w is a vector with positive integer entries, the alphabet 
is used by default. This yields [4,1,0,2] with our example.
If the underlying letters are irrelevant, the evaluation may be represented as a partition such as [4,2,1] in the example above.
evaluation – evaluation of a word, as an integer vector
combinat::words::evaluation(word w, <alphabet A>)
Returns the evaluation of w as an integer vector.
evaluationPartition – evaluation of a word, as a partition
combinat::words::evaluationPartition(word w)
Returns the evaluation of w as a partition.
evaluationTable – evaluation of a word, as a table
combinat::words::evaluationTable(word w)
Returns the evaluation of w as a table.
evaluationSparse – evaluation of a word, as a table
combinat::words::evaluationSparse(word w)
Returns the evaluation of w as a sorted associative list.
The letters are sorted with sort.
This method is likely to be renamed.
fromStandardAndEvaluation – word from its standard permutation and evaluation
combinat::words::fromStandardAndEvaluation(standard permutation p, evaluation e, <alphabet A>)
Returns the word whose standard permutation is p and whose evaluation (as an integer vector) is e.
Shuffle product of words
shuffle – shuffle product of two words
combinat::words::shuffle(word w1, word w2)
Returns the list of the words in the shuffle product of w1 and w2.
This is in fact a full featured combinatorial class, with the usual count, generator, and list methods (see below).
shuffle::count – number of words in the shuffle product of two words
combinat::words::shuffle::count(word w1, word w2)
Returns the number of words in the shuffle product of w1 and w2.
shuffle::generator – generator for the words shuffle product of two words
combinat::words::shuffle::generator(word w1, word w2)
Returns a generator for the words in the shuffle product of w1 and w2.
shuffle::list – list of the words in the shuffle product of two words
combinat::words::shuffle::list(word w1, word w2)
Returns the list of the words in the shuffle product of w1 and w2.
shuffleAugmented – augmented shuffle product of two words
combinat::words::shuffleAugmented(word w1, word w2, <function plus>)
Returns the list of the words in the augmented shuffle product of w1 and w2. This product is similar to the shuffle product, except that the letters of w1 and w2 may also be added together.
With the optional parameter plus, one may specify the operation to use to combine letters instead of addition.
Comparison of words
lexLess – strict lexicographic comparison of words
combinat::words::lexLess(word w1, word w2)
Returns TRUE if w1 is strictly smaller than w2 w.r.t. the lexicographic order.
All the comparison functions currently require that the letters in w1 and w2 should be comparable with <. The degree comparison functions further require that the letters can be added with +, and the result compared with <. Finally, to compare lists of different size, we use consistently the convention that a non existent letter is strictly smaller than an existent letter.
degLexLess – strict degree lexicographic comparison of words
combinat::words::degLexLess(word w1, word w2)
Returns TRUE if w1 is strictly smaller than w2 w.r.t. the degree lexicographic order.
See combinat::words::lexLess for the constraints on the letters.
invLexLess – strict inverse lexicographic comparison of words
combinat::words::invLexLess(word w1, word w2)
Returns TRUE if w1 is strictly smaller than w2 w.r.t. the inverse lexicographic order.
See combinat::words::lexLess for the constraints on the letters.
degInvLexLess – strict degree inverse lexicographic comparison of words
combinat::words::degInvLexLess(word w1, word w2)
Returns TRUE if w1 is strictly smaller than w2 w.r.t. the degree inverse lexicographic order.
Currently, the letters in w1 and w2 should be comparable with <, and addable by +.
revLexLess – strict reverse lexicographic comparison of words
combinat::words::revLexLess(word w1, word w2)
Returns TRUE if w1 is strictly smaller than w2 w.r.t. the reverse lexicographic order.
See combinat::words::lexLess for the constraints on the letters.
degRevLexLess – strict degree reverse lexicographic comparison of words
combinat::words::degRevLexLess(word w1, word w2)
Returns TRUE if w1 is strictly smaller than w2 w.r.t. the degree reverse lexicographic order.
See combinat::words::lexLess for the constraints on the letters.
Coplactic operations
The coplactic operations are the linear operators 
, 
(also known as the crystal operators) and 
(which corresponds to the action of the symmetric group algebra on the free algebra). See Lascoux A., Leclerc B. and Thibon J-Y., "The Plactic Monoid", in Lothaire (2002) Algebraic Combinatorics on Words. Cambridge University Press.
symmetricGroupActionOnValues – action of the symmetric group on a word
combinat::words::symmetricGroupActionOnValues(word w, permutation p)
Returns the result of the action of any reduced word of p over w.
crystalE – crystal operator e
combinat::words::crystalE(word w, any type i)
Returns the result of the action of the crystal operator 
on w.
crystalF – crystal operator f
combinat::words::crystalF(word w, any type i)
Returns the result of the action of the crystal operator 
on w.
Miscellaneous
swap – swap two (consecutive) letters in a word
combinat::words::swap(word w, integer i, <integer j>)
Swap the entries at positions i and j in the word w.
The default value for j is i+1, to swap two consecutive letters.
When speed is really critical, using the following alias is about four times faster on small lists: alias(swap(w,i,j) = subsop(w, i=w[i+1], i+1=w[i])).
Complexity: ought to be constant time. Seems to be linear!
swapIncrease – swap increasingly two consecutive letters in a word
combinat::words::swapIncrease(word w, integer i)
Swap the entries at positions i and i+1 in the word w if w[i]>w[i+1].
This method is likely to be renamed.
swapDecrease – swap decreasingly two consecutive letters in a word
combinat::words::swapDecrease(word w, integer i)
Swap the entries at positions i and i+1 in the word w if w[i]<w[i+1].
This method is likely to be renamed.
hammingDistance – Hamming distance between two words
combinat::words::hammingDistance(word w1, word w2)
Returns the Hamming distance between the words w1 and w2. This is the number of positions where the two words differ. If one word is longer than the other, then its extra letters are considered as different from the missing ones of the other.
There are 
words of length 
on the alphabet {a,b}:
combinat::words::count([a,b],3)
Here is the list:
combinat::words::list([a,b],3)
For the alphabet of [1,2], it is shorter to write:
combinat::words::count(2,3);
combinat::words::list(2,3);
When you want to run through the words, you can generate them one by one to save memory:
g := combinat::words::generator([a,b],3):
g();
g(), g(), g(), g(), g(), g(), g(), g();
h := combinat::words::generator(2,3):
h();
h(), h(), h(), h(), h(), h(), h(), h();
Typically, this would be used as follows:
g := combinat::words::generator(2,2):
while (p := g()) <> FAIL do print(p): end:
[1, 1]
[1, 2]
[2, 1]
[2, 2]
Most operations on words, such as standardization, depends on an alphabet ordering. You can get the ordering function associated with an alphabet with combinat::words::alphabetToOrder:
isSmaller := combinat::words::alphabetToOrder([c,b,a,d]):
isSmaller(a,b), bool(isSmaller(a,b));
isSmaller(a,d), bool(isSmaller(a,d));
Note that isSmaller does not return a boolean value but rather an expression whose evaluation is boolean.
If the alphabet is given by means of a set, an unspecified fixed order is chosen:
isSmaller := combinat::words::alphabetToOrder({c,b,a,d}):
isSmaller(a,b), bool(isSmaller(a,b));
isSmaller(a,d), bool(isSmaller(a,d));
2 < 3, TRUE
2 < 1, FALSE
You can compute the standard permutation of a word:
combinat::words::standard([1,2,3,2,2,1,2,1])
The standard permutation of a word and the word itself have by definition the same inversions (see combinat::permutations::inversions):
combinat::permutations::inversions([1,2,3,2,2,1,2,1]);
combinat::permutations::inversions(
combinat::words::standard([1,2,3,2,2,1,2,1]));
If your word is on an alphabet which cannot be ordered with <, you have to specify the order:
combinat::words::standard([a,b,a,c,b,c,a]);
Error: Can't evaluate to boolean [_less];
during evaluation of 'combinat::words::standard'
You can do that by specifying explicitly the alphabet:
combinat::words::standard([a,b,a,c,b,c,a],[a,b,c,d]);
Another way is to provide an ordering function:
isSmaller := (x,y) -> (expr2text(x) < expr2text(y)):
combinat::words::standard([a,b,a,c,b,c,a],isSmaller);
You can compute the shuffle product of two words:
combinat::words::shuffle([1,2,3],[a,b]);
You can also obtain them through a generator:
g:=combinat::words::shuffle::generator([1,2,3],[a,b]):
g(); g();
g() $ i=1..9;
Finally, here is the list of the words in the augmented shuffle product of [1,2] and [a,b]:
combinat::words::shuffleAugmented([1, 2], [a, b])
We demonstrate the use of some coplactic operations. We can compute the action of the permutation [1,3,2] on the word [2,2,3,1,1,2,2,3]:
combinat::words::symmetricGroupActionOnValues([2, 2, 3, 1, 1, 2, 2, 3], [1, 3, 2])
Here is the result of the action of the crystal operator 
on the same word:
combinat::words::crystalE([2, 2, 3, 1, 1, 2, 2, 3], 2)
and that of the crystal operator 
:
combinat::words::crystalF([2, 2, 3, 1, 1, 2, 2, 3], 2)
