combinat::words
--
words
The library combinat::words
provides functions for counting,
generating, and manipulating words.
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.Cat::CombinatorialClass
The MuPAD domain used to represent words: DOM_LIST
isA(word w, <alphabet A, size k>)
isA(word w, <nonnegative integer n, size k>)
w
is a word. If the alphabet or the size is
given check also if w
is of length k
on the alphabet
A
or [1,2,...,n]
.
list(alphabet A, nonnegative integer k)
list(nonnegative integer n, nonnegative integer k)
k
on the
alphabet A
or [1,2,...,n]
.
generator(alphabet A, nonnegative integer k)
generator(nonnegative integer n, nonnegative integer k)
k
on the
alphabet A
or [1,2,...,n]
.
alphabetToOrder(alphabet A)
A
. Such a
function takes two element x
and y
of A
and
returns TRUE
if x
occurs before y
in A
.
standard(word w)
standard(word w, alphabet A)
standard(word w, ordering o)
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.
shuffle(word w1, word w2)
w1
and w2
.
shuffle::generator(word w1, word w2)
w1
and w2
.
shuffleAugmented(word w1, word w2)
w1
and w2
.
lexLess(word w1, word w2)
w1
is strictly smaller than w1
w.r.t. the
lexicographic order.w1
and w1
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(word w1, word w2)
w1
is strictly smaller than w1
w.r.t. the
degree lexicographic order.combinat::words::lexLess
for the constraints on the letters.
invLexLess(word w1, word w2)
w1
is strictly smaller than w1
w.r.t. the inverse lexicographic order.combinat::words::lexLess
for the constraints on the letters.
degInvLexLess(word w1, word w2)
w1
is strictly smaller than w1
w.r.t. the
degree inverse lexicographic order.w1
and w1
should be
comparable with <
, and addable by +
.
revLexLess(word w1, word w2)
w1
is strictly smaller than w1
w.r.t. the reverse lexicographic order.combinat::words::lexLess
for the constraints on the letters.
degRevLexLess(word w1, word w2)
w1
is strictly smaller than w1
w.r.t. the
degree reverse lexicographic order.combinat::words::lexLess
for the constraints on the letters.There are 8 words of length 3 on the alphabet
{a,b}
:
>> combinat::words::count([a,b],3)
8
Here is the list:
>> combinat::words::list([a,b],3)
[[a, a, a], [a, a, b], [a, b, a], [a, b, b], [b, a, a], [b, a, b], [b, b, a], [b, b, b]]
For the alphabet of [1,2]
, it is shorter to write:
>> combinat::words::count(2,3);
combinat::words::list(2,3);
8 [[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2, 2, 1], [2, 2, 2]]
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();
[a, a, a] [a, a, b], [a, b, a], [a, b, b], [b, a, a], [b, a, b], [b, b, a], [b, b, b], FAIL [1, 1, 1] [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2, 2, 1], [2, 2, 2], FAIL
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));
3 < 2, FALSE 3 < 4, TRUE
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])
[1, 4, 8, 5, 6, 2, 7, 3]
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]));
[{2, 6}, {2, 8}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {4, 6}, {4, 8}, {5, 6}, {5, 8}, {7, 8}] [{2, 6}, {2, 8}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {4, 6}, {4, 8}, {5, 6}, {5, 8}, {7, 8}]
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]);
[1, 4, 2, 6, 5, 7, 3]
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);
[1, 4, 2, 6, 5, 7, 3]
You can compute the shuffle product of two words:
>> combinat::words::shuffle([1,2,3],[a,b]);
[[1, 2, 3, a, b], [1, 2, a, 3, b], [1, 2, a, b, 3], [1, a, 2, 3, b], [1, a, 2, b, 3], [1, a, b, 2, 3], [a, 1, 2, 3, b], [a, 1, 2, b, 3], [a, 1, b, 2, 3], [a, b, 1, 2, 3]]You can also obtain them through a generator:
>> g:=combinat::words::shuffle::generator([1,2,3],[a,b]):
g(); g();
g() $ i=1..9;
[1, 2, 3, a, b] [1, 2, a, 3, b] [1, 2, a, b, 3], [1, a, 2, 3, b], [1, a, 2, b, 3], [1, a, b, 2, 3], [a, 1, 2, 3, b], [a, 1, 2, b, 3], [a, 1, b, 2, 3], [a, b, 1, 2, 3], FAIL
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])
[[a, b, 1, 2], [a, 1, b, 2], [1, a, b, 2], [a + 1, b, 2], [a, b + 1, 2], [a, 1, 2, b], [1, a, 2, b], [a + 1, 2, b], [1, 2, a, b], [1, a + 2, b], [a, 1, b + 2], [1, a, b + 2], [a + 1, b + 2]]
Ax::systemRep
MuPAD Combinat, an open source algebraic combinatorics package