[Previous] [Next] [Contents]

[ImplState=stable,TestState=stable,DocState=stable]

## `combinat::permutations` -- permutations

#### Introduction

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

Further functions are documented theme by theme in separate help pages:

- inversions and code of permutations `combinat::permutations::inversions`,
- cycle decompositions of permutations `combinat::permutations::cycles`,
- descents set of permutations `combinat::permutations::descents`.
- Bruhat order `combinat::permutations::leequalBruhat`.
- permutoedron order `combinat::permutations::leequalPermutoedron`.
- peaks of permutations `combinat::permutations::peaks`.
- saillances of permutations `combinat::permutations::saillances`.
- patterns in permutations `combinat::permutations::haspattern`.

#### Details

- A permutation of a list `l` is a list of the same size obtained by some reordering of the elements of `l`.

- A standard permutation is a permutation of the list `[1,2,...,n]`, for some positive integer `n`. For standard permutations, the manipulating functions accept the number `n` as parameter instead of the list `[1,2,...,n]`.

- Several functions accept the option Duplicate. This option specifies whether two reorderings of the elements of `l` that are the same list are considered as distinct or not. Hence, without the option Duplicate, the permutations of `l` are all distinct lists obtained by permuting the elements of `l`. With the option Duplicate, a list of size `n` exactly has `n!` permutations, that are not necessarily distinct lists.

- Without the option Duplicate, the permutations are generated and listed in lexicographic order.

#### Categories

`Cat::CombinatorialClass`

#### Related Domains

`combinat::words`

#### Entries

domtype

The MuPAD domain used to represent permutations: `DOM_LIST`

typeStandard

The MuPAD type used to represent standard permutations.

#### Method isA: test if an object is a permutations

- `isA(any type perm)`

- Returns whether `perm` is a permutations.

- `isA(any type perm, word wrd)`

- Returns whether `perm` is a permutations of the word `wrd`.

- `isA(any type perm, nonnegative integer n)`

- Returns whether `perm` is a permutations of the list `[1..n]`.

#### Method isAStandard: test if an object is a standard permutations

- `isAStandard(any type perm)`

- Returns whether `perm` is a standard permutations.

#### Method count: number of permutations

- `count(list l <, Duplicate>)`

- Returns the number of permutations of the list `l`, with or without duplicates.

- `count(nonnegative integer n)`

- Returns the number of permutations of the list `[1,...,n]`.

#### Method list: list of the permutations

- `list(list l <, Duplicate>)`

- Returns the list of the permutations of the list `l`, with or without duplicates.

- `list(nonnegative integer n)`

- Returns the list of the permutations of the list `[1,...,n]`.

#### Method generator: generator for permutations

- `generator(list l <, Duplicate>)`

- Returns a generator for the permutations of the list `l`, with or without duplicates.

- `generator(nonnegative integer n)`

- Returns a generator for the permutations of the list `[1,...,n]`.

#### Method first: first permutation

- `first(list l)`

- Returns the first permutation of the list `l` in lexicographic order. This is equivalent to `sort(l)`.

- `first(nonnegative integer n)`

- Returns the first permutation of the list `[1,...,n]`, that is `[1,...,n]`.

#### Method last: last permutation

- `last(list l)`

- Returns the last permutation of the list `l` in lexicographic order. This is equivalent to `revert(sort(l))`.

- `last(nonnegative integer n)`

- Returns the last permutation of the list `[1,...,n]`, that is `[n,...,1]`.

#### Method Next: next permutation

- `Next(numerical list l)`

- Returns the next permutation of the list `l` in lexicographic order.
- `Next` cannot deal with duplications, nor with lists whose elements cannot be ordered by `<`.

#### Method previous: previous permutation

- `previous(numerical list l)`

- Returns the previous permutation of the list `l` in lexicographic order.
- `previous` can not deal with duplications, nor with lists whose elements cannot be ordered by `<`.

#### Method rank: rank of a permutation

- `rank(standard permutation p)`

- Returns the rank r of a permutation `p` of size n, this permutation being by definition the r-th one in the list of all permutations of size n lexicographically sorted.
- `rank` cannot deal with duplications, nor with lists whose elements cannot be ordered by `<`.

#### Method unrank: permutation unranked

- `unrank(nonnegative integer r, nonnegative integer n)`

- Returns the permutation of rank r in the list of standard permutations of size n lexicographically sorted.

#### Method random: random permutation

- `random(list l)`

- Returns a random permutation of the list `l`.

- `random(nonnegative integer n)`

- Returns a random permutation of the list `[1,...,n]`.

#### Method inverse: inverse of a standard permutation

- `inverse(standard permutation p)`

- Returns the inverse of the standard permutation `p`.

#### Method _mult: Action and composition of permutations

- `_mult(word w, standard permutation p)`
- `_mult(standard permutation p1, standard permutation p2)`

- Returns the action of the standard permutation `p` on the word `w` (action on the right). If `p1` is a standard permutation, it performs the composition of `p1` and `p2` (as p1 p2, `p2` acting on the right of `p1`).

#### Method toMatrix: permutation matrix of a standard permutation

- `toMatrix(standard permutation p)`

- Returns the permutation matrix of the standard permutation `p` seen as an endomorphism of the symmetric group algebra.
- Known bug: `toMatrix` does not work for the trivial permutation `[]`.

#### Example 1

There are 6 permutations of the list `[a,b,c]`:

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

                                         6

Here is the list:

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

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

             [c, b, a]]

For the permutations of `[1,2,3]`, it is shorter to write:

    >> combinat::permutations::count(3);
       combinat::permutations::list(3);

                                         6

          [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2],

             [3, 2, 1]]

You can use the function `combinat::permutations::first` to get the ``first'' permutation of a list or the first standard permutation of a given size:

    >> combinat::permutations::first([c, b, a, d]);
       combinat::permutations::first(4)

                                   [a, b, c, d]

                                   [1, 2, 3, 4]

Using `combinat::permutations::Next`, you can calculate the ``next'' permutation. This function takes as argument the permutation relative to which you want the next one:

    >> combinat::permutations::Next([1, 3, 2, 4])

                                   [1, 3, 4, 2]

`combinat::permutations::Next` returns `FAIL` when the input is the last permutation:

    >> combinat::permutations::Next([4, 3, 2, 1])

                                       FAIL

You can also go backward with `combinat::permutations::last` and `combinat::permutations::previous`

    >> combinat::permutations::last([1, 2, 3, 4]);
       combinat::permutations::previous([1, 3, 2, 4]);

                                   [4, 3, 2, 1]

                                   [1, 2, 4, 3]

When you want to run through the permutations of a list, you can generate them one by one to save memory:

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

                                     [1, 2, 3]

            [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], FAIL

                                     [a, b, c]

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

Typically, this would be used as follows:

    >> g := combinat::permutations::generator(3):
       while (p := g()) <> FAIL do print(p): end:

                                     [1, 2, 3]

                                     [1, 3, 2]

                                     [2, 1, 3]

                                     [2, 3, 1]

                                     [3, 1, 2]

                                     [3, 2, 1]

#### Example 2

By default, the permutations of a given list are all distinct lists obtained by permuting its elements:

    >> combinat::permutations::count([a, a, b]);
       combinat::permutations::list([a, a, b]);

                                         3

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

To consider reorderings with multiplicities, one can use the Duplicate option:

    >> combinat::permutations::count([a, a, b], Duplicate);
       combinat::permutations::list([a, a, b], Duplicate);

                                         6

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

             [b, a, a]]

Note that with the option Duplicateas above, the permutations are not guaranted to be listed in lexicographic order.

#### Example 3

You can get the rank of a permutation using:

    >> combinat::permutations::rank([3, 6, 5, 4, 2, 1]);

                                        360

Conversely, you can recover the permutation of rank r and size n using:

    >> combinat::permutations::unrank(360,6);

                                [3, 6, 5, 4, 2, 1]

#### Example 4

Here is the way to get a random permutation:

    >> combinat::permutations::random([a,a,b,c,d,d,e,f]);
       combinat::permutations::random(10);

                             [d, b, c, f, e, a, d, a]

                          [8, 1, 2, 6, 4, 9, 7, 10, 3, 5]

#### Example 5

It is sometime useful to represent a standard permutation by its matrix:

    >> combinat::permutations::toMatrix([2, 4, 1, 5, 3]);

                                +-               -+
                                |  0, 0, 1, 0, 0  |
                                |                 |
                                |  1, 0, 0, 0, 0  |
                                |                 |
                                |  0, 0, 0, 0, 1  |
                                |                 |
                                |  0, 1, 0, 0, 0  |
                                |                 |
                                |  0, 0, 0, 1, 0  |
                                +-               -+

The inverse permutation is computed by:

    >> combinat::permutations::inverse([2, 4, 1, 5, 3])

                                  [3, 1, 5, 2, 4]

It corresponds to the transpose matrix:

    >> combinat::permutations::toMatrix(
          combinat::permutations::inverse([2,4,1, 5, 3])),
       linalg::transpose(
          combinat::permutations::toMatrix([2,4, 1, 5, 3]))

                     +-               -+  +-               -+
                     |  0, 1, 0, 0, 0  |  |  0, 1, 0, 0, 0  |
                     |                 |  |                 |
                     |  0, 0, 0, 1, 0  |  |  0, 0, 0, 1, 0  |
                     |                 |  |                 |
                     |  1, 0, 0, 0, 0  |, |  1, 0, 0, 0, 0  |
                     |                 |  |                 |
                     |  0, 0, 0, 0, 1  |  |  0, 0, 0, 0, 1  |
                     |                 |  |                 |
                     |  0, 0, 1, 0, 0  |  |  0, 0, 1, 0, 0  |
                     +-               -+  +-               -+

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package