[Previous] [Contents]

## `combinat::words` -- words

#### Introduction

The library `combinat::words` provides functions for counting, generating, and manipulating words.

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

#### Categories

`Cat::CombinatorialClass`

#### Entries

domtype

The MuPAD domain used to represent words: `DOM_LIST`

#### Method isA: check if an object is a word

- `isA(word w, <alphabet A, size k>)`
- `isA(word w, <nonnegative integer n, size k>)`

- Returns true if `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]`.

#### Method list: list of the words

- `list(alphabet A, nonnegative integer k)`
- `list(nonnegative integer n, nonnegative integer k)`

- Returns the list of the words of length `k` on the alphabet `A` or `[1,2,...,n]`.

#### Method generator: generator for words

- `generator(alphabet A, nonnegative integer k)`
- `generator(nonnegative integer n, nonnegative integer k)`

- Returns a generator for the words of length `k` on the alphabet `A` or `[1,2,...,n]`.

#### Method alphabetToOrder: ordering function of an alphabet

- `alphabetToOrder(alphabet A)`

- Returns the ordering function of the alphabet `A`. Such a function takes two element `x` and `y` of `A` and returns `TRUE` if `x` occurs before `y` in `A`.

#### Method standard: standard permutation of a word

- `standard(word w)`
- `standard(word w, alphabet A)`
- `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.

#### Method evaluation: [ImplState=stable,TestState=stable,DocState=alpha]

#### Method evaluationPartition: [ImplState=stable,TestState=beta,DocState=alpha]

#### Method evaluationTable: [ImplState=stable,TestState=stable,DocState=alpha]

#### Method fromStandardAndEvaluation: [ImplState=stable,TestState=stable,DocState=alpha]

#### Method shuffle: shuffle product of two words

- `shuffle(word w1, word w2)`

- Returns the list of the words in the shuffle product of `w1` and `w2`.

#### Method shuffle::generator: generator for the shuffle product of two words

- `shuffle::generator(word w1, word w2)`

- Returns a generator for the words in the shuffle product of `w1` and `w2`.

#### Method shuffleAugmented: augmented shuffle product of two words

- `shuffleAugmented(word w1, word w2)`

- Returns the list of the words in the augmented shuffle product of `w1` and `w2`.

#### Method lexLess: [ImplState=beta,TestState=beta,DocState=beta] strict lexicographic comparison of words

- `lexLess(word w1, word w2)`

- Returns TRUE if `w1` is strictly smaller than `w1` w.r.t. the lexicographic order.
- All the comparison functions currently require that the letters in `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.

#### Method degLexLess: [ImplState=beta,TestState=beta,DocState=beta] strict degree lexicographic comparison of words

- `degLexLess(word w1, word w2)`

- Returns TRUE if `w1` is strictly smaller than `w1` w.r.t. the degree lexicographic order.
- See `combinat::words::lexLess` for the constraints on the letters.

#### Method invLexLess: [ImplState=beta,TestState=alpha,DocState=beta] strict inverse lexicographic comparison of words

- `invLexLess(word w1, word w2)`

- Returns TRUE if `w1` is strictly smaller than `w1` w.r.t. the inverse lexicographic order.
- See `combinat::words::lexLess` for the constraints on the letters.

#### Method degInvLexLess: [ImplState=beta,TestState=beta,DocState=beta] strict degree inverse lexicographic comparison of words

- `degInvLexLess(word w1, word w2)`

- Returns TRUE if `w1` is strictly smaller than `w1` w.r.t. the degree inverse lexicographic order.
- Currently, the letters in `w1` and `w1` should be comparable with `<`, and addable by `+`.

#### Method revLexLess: [ImplState=beta,TestState=alpha,DocState=beta] strict reverse lexicographic comparison of words

- `revLexLess(word w1, word w2)`

- Returns TRUE if `w1` is strictly smaller than `w1` w.r.t. the reverse lexicographic order.
- See `combinat::words::lexLess` for the constraints on the letters.

#### Method degRevLexLess: [ImplState=beta,TestState=alpha,DocState=beta] strict degree reverse lexicographic comparison of words

- `degRevLexLess(word w1, word w2)`

- Returns TRUE if `w1` is strictly smaller than `w1` w.r.t. the degree reverse lexicographic order.
- See `combinat::words::lexLess` for the constraints on the letters.

#### Example 1

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]

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

#### Example 3

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]

#### Example 4

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

#### Super-Domain

`Dom::BaseDomain`

#### Axioms

`Ax::systemRep`

[Previous] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package