[Previous] [Next] [Contents]

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

## `combinat::permutations::leequalPermutoedron` -- permutoedron order on standard permutations

#### Introduction

Functions related to the permutoedron order on permutations.

#### Details

- The permutoedron order is a partial order defined on the elements of a given symmetric group, that is, on the permutations of a given size. It is also known under the name of ''weak Bruhat order''.

- There are two different orders whether one make the permutations act to the left or to the right on the symmetric group. By default, computations are done in the right permutoedron.

- A permutation p1 is smaller than a permutation p2 in the left (resp. right) permutoedron if and only if any reduced word of p1 is a suffix (resp. prefix) of one of the reduced word of p2.

- Equivalently, p1 is smaller than p2 in the left (resp. right) permutoedron if and only if one can go from p1 to p2 by multiplying p1 on the left (resp. right) by a sequence of elementary transpositions that increment at each step its number of inversions.

#### Method leequalPermutoedron: Test of the order relation of two permutations

- `leequalPermutoedron(standard permutations p1, p2 <, Left>)`

- Returns the boolean answering the question ''Is `p1` smaller than `p2` in the permutoedron order?''

- With no option given or with the option Right, computations are done in the Right permutoedron. With the option Left, computations are done in the Left permutoedron.

#### Method predPermutoedron: list of the precedessors of a permutation

- `predPermutoedron(standard permutation p <, Left>)`

- Returns the list of permutations strictly smaller than `p` in the permutoedron order, such that there is no permutation between one of those and `p`.

- With no option given or with the option Right, computations are done in the Right permutoedron. With the option Left, computations are done in the Left permutoedron.

#### Method succPermutoedron: list of the successors of a permutation

- `succPermutoedron(standard permutation p <, Left>)`

- Returns the list of permutations strictly greater than `p` in the permutoedron order, such that there is no permutation between `p` and one of those.

- With no option given or with the option Right, computations are done in the Right permutoedron. With the option Left, computations are done in the Left permutoedron.

#### Method smallerPermutoedron: list of the permutations smaller than a permutation

- `smallerPermutoedron(standard permutation p <, Left>)`

- Returns the list of permutations smaller than or equal to `p` in the permutoedron order.

- With no option given or with the option Right, computations are done in the Right permutoedron. With the option Left, computations are done in the Left permutoedron.

#### Method greaterPermutoedron: list of the permutations greater than a permutation

- `greaterPermutoedron(standard permutation p <, Left>)`

- Returns the list of permutations greater than or equal to `p` in the permutoedron order.

- With no option given or with the option Right, computations are done in the Right permutoedron. With the option Left, computations are done in the Left permutoedron.

#### Example 1

All the computations in this example are done in the Right permutoedron. To check whether a permutation is smaller than another thanks to the permutoedron order, you can use:

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

                                       FALSE

To compute what permutations precede a given permutation, you can use:

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

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

Now, you can compute the transitive ideal generated by the predecessor relation and get:

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

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

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

What was done with the permutations preceding a given one or smaller than it, can also be performed by the permutations succeeding a given one or greater than it by:

    >> combinat::permutations::succPermutoedron([4, 2, 1, 3]);
       combinat::permutations::greaterPermutoedron([4, 2, 1, 3]);

                                  [[4, 2, 3, 1]]

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

#### Example 2

All the computations in this example are done in the Left permutoedron. All the result can be compared with the results of the previous example. To check whether a permutation is smaller than another thanks to the permutoedron order, you can use:

    >> combinat::permutations::leequalPermutoedron([3,2,1,4],[4,2,1,3],Left);

                                       TRUE

To compute what permutations precede a given permutation in the Left permutoedron, you can use:

    >> combinat::permutations::predPermutoedron([4, 2, 1, 3], Left);

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

Now, you can compute the transitive ideal generated by the predecessor relation in the Left permutoedron and get:

    >> combinat::permutations::smallerPermutoedron([4, 2, 1, 3], Left);

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

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

What was done with the permutations preceding a given one or smaller than it, can also be performed by the permutations succeeding a given one or greater than it by:

    >> combinat::permutations::succPermutoedron([4, 2, 1, 3], Left);
       combinat::permutations::greaterPermutoedron([4, 2, 1, 3], Left);

                                  [[4, 3, 1, 2]]

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

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package