[Previous] [Next] [Contents]

## `combinat::subwords` -- subwords of a word

#### Introduction

The library `combinat::subwords` provides functions for counting, generating, and manipulating the subwords of a word.

#### Details

- A subword of a word w is a word obtained by deleting the letters at some of the positions in w (see also `combinat::words`). A subword is generated as many times as it appears in the word.
- Sometimes, a letter in the word w can be repeated several times in the subword, even it only appears once in w. This is done with the option Repeat.

#### Categories

`Cat::CombinatorialClass`

#### Related Domains

`combinat::words`

#### Entries

domtype

The MuPAD domain used to represent subwords: `DOM_LIST`.

#### Method count: number of subwords of a word

- `count(word A)`

- Returns the number of subwords of a word.

- `count(word A, nonnegative integer k <, Repeat>)`

- Returns the number of subwords of length k of a word, with optional repetition of letters.

#### Method list: list of the subwords of a word

- `list(word A)`

- Returns the list of the subwords of a word.

- `list(word A, nonnegative integer k <, Repeat>)`

- Returns the list of the subwords of length k of a word, with optional repetition of letters.

#### Method generator: generator for subwords of a word

- `generator(word A)`

- Returns a generator for subwords of a word.

- `generator(word A, nonnegative integer k <, Repeat>)`

- Returns a generator for subwords of length k of a word, with optional repetition of letters.

#### Method first: first subword of a word

- `first(word A)`

- Returns the first subword of a word.

- `first(word A, nonnegative integer k <, Repeat>)`

- Returns the first subword of length k of a word, with optional repetition of letters.

#### Method last: last subword of a word

- `last(word A)`

- Returns the last subword of a word.

- `last(word A, nonnegative integer k <, Repeat>)`

- Returns the first subword of length k of a word, with optional repetition of letters.

#### Example 1

There are 8 subwords of the word `[a, c, b]`:

    >> combinat::subwords::count([a, c, b])

                                         8

Here is the list:

    >> combinat::subwords::list([a, b, c])

              [[], [a], [b], [c], [a, b], [a, c], [b, c], [a, b, c]]

To compute the subwords of a given length:

    >> combinat::subwords::count([a, c, b, b, c], 3);
       combinat::subwords::list([a, c, b, b, c], 3)

                                        10

          [[a, c, b], [a, c, b], [a, c, c], [a, b, b], [a, b, c],

             [a, b, c], [c, b, b], [c, b, c], [c, b, c], [b, b, c]]

Note that the word `[a, c, b]` is repeated twice.

When you want to run through the subwords, you can generate them one by one to save memory:

    >> g := combinat::subwords::generator([a, c, b, b, c], 3):
       g(), g();
       g(), g(), g(), g(), g(), g(), g(), g(), g();

                               [a, c, b], [a, c, b]

          [a, c, c], [a, b, b], [a, b, c], [a, b, c], [c, b, b],

             [c, b, c], [c, b, c], [b, b, c], FAIL

Typically, this would be used as follows:

    >> g := combinat::subwords::generator([a, b, b, a], 2):
       while (p := g()) <> FAIL do print(p): end:

                                      [a, b]

                                      [a, b]

                                      [a, a]

                                      [b, b]

                                      [b, a]

                                      [b, a]

The ``first'' and ``last'' subwords of length k, also called left and right factors are computed in this example:

    >> combinat::subwords::first([a, b, b, a, d, b, a], 3);
       combinat::subwords::last([a, b, b, a, d, b, a], 3);

                                     [a, b, b]

                                     [d, b, a]

#### Example 2

To list the non-decreasing words of `[a, b, d]`, you just have to list the subwords of `[a, b, d]` with repetitions:

    >> combinat::subwords::list([a, b, d], 3, Repeat);

          [[a, a, a], [a, a, b], [a, a, d], [a, b, b], [a, b, d],

             [a, d, d], [b, b, b], [b, b, d], [b, d, d], [d, d, d]]

It also works for an input word with repeated letters:

    >> combinat::subwords::list([a, b, b], 3, Repeat);

          [[a, a, a], [a, a, b], [a, a, b], [a, b, b], [a, b, b],

             [a, b, b], [b, b, b], [b, b, b], [b, b, b], [b, b, b]]

And also with generators:

    >> g := combinat::subwords::generator([a, b, b], 3, Repeat):
       g(), g();
       g(), g(), g(), g(), g(), g(), g(), g(), g();

                               [a, a, a], [a, a, b]

          [a, a, b], [a, b, b], [a, b, b], [a, b, b], [b, b, b],

             [b, b, b], [b, b, b], [b, b, b], FAIL

#### Super-Domain

`Dom::BaseDomain`

#### Axioms

`Ax::systemRep`

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package