It has been of interest to the authors to compute different properties of permutations. Inspections include plus- and minus-decomposable permutations, block-decompositions of permutations, as well as the computation of the direct and skew sum of permutations. First a couple of definitions on which some of the properties are based on:

An interval of a permutation \(\sigma\) is a set of contiguous values which in \(\sigma\) have consecutive indices.

A permutation of length \(n\) is called simple if it only contains the intervals of length 0, 1 and \(n\).

As mentioned above, an interval of a permutation \(\sigma\) is a set of contiguous numbers which in \(\sigma\) have consecutive indices. For example in \(\sigma = 4 6 8 7 1 5 2 3 \) the following is an interval \(\sigma(2)\sigma(3)\sigma(4)=6 8 7\) whereas \(\sigma(4)\sigma(5)\sigma(6)=7 1 5\) is not.

`‣ IsInterval` ( list ) | ( function ) |

Returns: `true`

, if `list`

is an interval.

IsInterval takes in any list with unique elements, which can be ordered lexicographically and checkes whether it is an interval.

gap> IsInterval([3,6,9,2]); false gap> IsInterval([2,6,5,3,4]); true gap>

As mentioned above a permutation is said to be simple if it only contains intervals of length 0, 1 or the length of the permutation.

`‣ IsSimplePerm` ( perm ) | ( function ) |

Returns: `true`

if `perm`

is simple.

To check whether `perm`

(length of `perm`

= \(n\)) is a simple permutation `IsSimplePerm`

uses the basic algorithm proposed by Uno and Yagiura in [UY00] to compare the `perm`

against the identity permutation of the same length.

gap> IsSimplePerm([2,3,4,5,1,1,1,1]); true gap> IsSimplePerm([2,4,6,8,1,3,5,7]); true gap> IsSimplePerm([3,2,8,6,7,1,5,4]); false gap>

In [PR12] it is shown how one can get chains of permutations by starting with a simple permutation and then removing either a single point or two points and the resulting permutation would still be simple. We have applied this theory to create functions such that the set of simple permutations of shorter length, by one deletion, can be found.

`‣ OnePointDelete` ( perm ) | ( function ) |

Returns: A list of simple permutations with one point less than `perm`

.

`OnePointDelete`

removes single points in the simple permutation and returns a list of the resulting simple permutations, in their rank encoding.

gap> OnePointDelete([5,2,3,1,2,1]); [ [ 2, 3, 1, 2, 1 ], [ 4, 1, 2, 2, 1 ] ] gap> OnePointDelete([5,2,4,1,6,3]); [ [ 2, 3, 1, 2, 1 ], [ 4, 1, 2, 2, 1 ] ] gap>

`‣ TwoPointDelete` ( perm ) | ( function ) |

Returns: The exceptional permutation with two point less than `perm`

.

`TwoPointDelete`

removes two points of the input exceptional permutation and returns the list of the unique resulting permutation, in its rank encoding.

gap> TwoPointDelete([2,4,6,8,1,3,5,7]); [ [ 2, 3, 4, 1, 1, 1 ] ] gap> TwoPointDelete([2,3,4,5,1,1,1,1]); [ [ 2, 3, 4, 1, 1, 1 ] ] gap>

`‣ PointDeletion` ( perm ) | ( function ) |

Returns: A list of simple permutations with of shorter length than `perm`

.

`PointDeletion`

takes any simple permutation does not matter whether exceptional or not and removes the right number of points.

gap> PointDeletion([5,2,3,1,2,1]); [ [ 2, 3, 1, 2, 1 ], [ 4, 1, 2, 2, 1 ] ] gap> PointDeletion([5,2,4,1,6,3]); [ [ 2, 3, 1, 2, 1 ], [ 4, 1, 2, 2, 1 ] ] gap> PointDeletion([2,4,6,8,1,3,5,7]); [ [ 2, 3, 4, 1, 1, 1 ] ] gap> PointDeletion([2,3,4,5,1,1,1,1]); [ [ 2, 3, 4, 1, 1, 1 ] ] gap>

Given a permutation \(\pi\) of length \(m\) and nonempty permutations \(\alpha_{1},\ldots,\alpha_{m}\) the inflation of \(\pi\) by \(\alpha_{1},\ldots,\alpha_{m}\), written as \(\pi[\alpha_{1},\ldots,\alpha_{m}]\), is the permutation obtained by replacing each entry \(\pi(i)\) by an interval that is order isomorphic to \(\alpha_{i}\) [Bri08]. Conversely a block-decomposition of \(\sigma\) is any expression of \(\sigma\) as an inflation \(\sigma=\pi[\alpha_{1},\ldots,\alpha_{m}]\). The block decomposition of a permutation is unique if and only if \(\sigma,\pi,\alpha_{1},\ldots,\alpha_{n}\) all are in the same pattern class and \(\pi\) is simple and \(\pi\neq 1 2,\ 2 1\) [AA05].

For example the inflation of \(25413[21,1,1,1,2413]=3 2 8 9 1 5 7 4 6\), written in **GAP** this is `[[2,5,4,1,3],[2,1],[1],[1],[1],[2,4,1,3]]`

. This decomposition of \(3 2 8 9 1 5 7 4 6\) is not unique. The unique block-decomposition, as described above, for \(3 2 8 9 1 5 7 4 6=2413[21,12,1,2413]\) or in **GAP** notation `[3,2,8,9,1,5,7,4,6]=[[2,4,1,3],[2,1],[1,2],[1],[2,4,1,3]]`

.

`‣ Inflation` ( list_of_perms ) | ( function ) |

Returns: A permutation that represents the inflation of the list of permutations, taking the first permutation to be \(\pi\), as described in the definition of inflation.

Inflation takes the list of permutations that stand for a box decomposition of a permutation, and calculates that permutation by replacing each entry \(i\) in the first permutation by an interval order isomorphic to the permutation in index \(i+1\).

gap> Inflation([[3,2,1],[1],[1,2],[1,2,3]]); [ 6, 4, 5, 1, 2, 3 ] gap> Inflation([[1,2],[1],[4,2,1,3]]); [ 1, 5, 3, 2, 4 ] gap> Inflation([[2,4,1,3],[2,1],[3,1,2],[1],[2,4,1,3]]); [ 3, 2, 10, 8, 9, 1, 5, 7, 4, 6 ] gap>

`‣ BlockDecomposition` ( perm ) | ( function ) |

Returns: A list of permutations, representing the block-decomposition of `perm`

. In the list the first permutation is \(\pi\), as described in the definiton of block-decomposition above.

`BlockDecomposition`

takes a plus- and minus-indecomposable permutation and decomposes it into its maximal maximal intervals, which are preceded by the simple permutation that represents the positions of the intervals. If a plus- or minus-decomposable permutation is input, then the decomposition will not be the unique decomposition, by the definition of plus- or minus- decomposable permutations, see below.

gap> BlockDecomposition([3,2,10,8,9,1,5,7,4,6]); [ [ 2, 4, 1, 3 ], [ 2, 1 ], [ 3, 1, 2 ], [ 1 ], [ 2, 4, 1, 3 ] ] gap> BlockDecomposition([1,2,3,4,5]); [ [ 1, 2 ], [ 1, 2, 3, 4 ], [ 1 ] ] gap> BlockDecomposition([5,4,3,2,1]); [ [ 2, 1 ], [ 4, 3, 2, 1 ], [ 1 ] ] gap>

A permutation \(\sigma\) is said to be plus-decomposable if it can be written uniquely in the following form,

\[\sigma = 12 [\alpha_{1},\alpha_{2}] \]

where \(\alpha_{1}\) is not plus-decomposable.

The subset of a rational class, containing all permutations that are plus-decomposable and in the class, has been found to be also rational under the rank encoding.

`‣ IsPlusDecomposable` ( perm ) | ( function ) |

Returns: `true`

if `perm`

is plus-decomposable.

To check whether `perm`

is a plus-decomposable permutation `IsPlusDecomposable`

uses the fact that there has to be an interval \(1..x\) where \(x <n\) (\(n\) = length of the `perm`

) in the rank encoded permutation that is a valid rank encoding.

gap> IsPlusDecomposable([3,3,2,3,2,2,1,1]); true gap> IsPlusDecomposable([3,4,2,6,5,7,1,8]); true gap> IsPlusDecomposable([3,2,8,6,7,1,5,4]); false gap>

Minus-decomposability is essentially the same as plus-decomposability, the difference is that if a permutation \(\sigma\) is minus-decomposable, it can be written uniquely in the following form,

\[\sigma = 21 [\alpha_{1},\alpha_{2}] \]

where \(\alpha_{1}\) is not minus-decomposable.

Here also, the subset of a rational class, containing all permutations that are minus-decomposable and in the class, has been found to be rational under the rank encoding.

`‣ IsMinusDecomposable` ( perm ) | ( function ) |

Returns: `true`

if `perm`

is minus-decomposable.

To check whether `perm`

(length of `perm`

= \(n\)) is a minus-decomposable permutation `IsMinusDecomposable`

uses the fact that the first \(n-x\), where \(x<n\), letters in the rank encoding of `perm`

have to be \(>x\) and that the letters from position \(x+1\) until the last one have to be \(\leq x\).

gap> IsMinusDecomposable([3,3,3,3,3,3,2,1]); true gap> IsMinusDecomposable([3,4,5,6,7,8,2,1]); true gap> IsMinusDecomposable([3,2,8,6,7,1,5,4]); false gap>

The direct sum of two permutations \(\sigma=\sigma_{1} \ldots \sigma_{k}\) and \(\tau=\tau_{1}\ldots\tau_{l}\) is defined as,

\[\sigma \oplus \tau = \sigma_{1}\ \ \sigma_{2}\ldots\sigma_{k}\ \ \tau_{1}+k\ \ \tau_{2}+k\ldots\tau_{l}+k\ .\]

In a similar fashion the skew sum of \(\sigma, \tau\) is

\[\sigma \ominus \tau = \sigma_{1}+l\ \ \sigma_{2}+l\ldots\sigma_{k}+l\ \ \tau_{1}\ \tau_{2}\ldots\tau_{l}\ .\]

The calculation of the direct and skew sums of permutations using the rank encoding is also straight forward and is used in the functions described below. The direct sum of two permutations \(\sigma,\tau\) represented as their rank encoded sequences is the permutation which has the rank encoding that is the concatention of the rank encoding of \(\sigma\) and \(\tau\). The skew sum of two permutations \(\sigma,\tau\) encoded by the rank encoding is the concatenation of the rank encodings of \(\sigma\) and \(\tau\) where in the sequence corresponding to \(\sigma\) under the rank encoding each element has been increased by \(l\), with \(l\) being the length of \(\tau\).

`‣ PermDirectSum` ( perm1, perm2 ) | ( function ) |

Returns: A permutation resulting from `perm1`

\(\oplus\) `perm2`

.

`PermDirectSum`

returns the permutation corresponding to `perm1`

\(\oplus\) `perm2`

if `perm1`

and `perm2`

are both not rank encoded. If both `perm1`

and `perm2`

are rank encoded, then `PermDirectSum`

returns a rank encoded sequence.

gap> PermDirectSum([2,4,1,3],[2,5,4,1,3]); [ 2, 4, 1, 3, 6, 9, 8, 5, 7 ] gap> PermDirectSum([2,3,1,1],[2,4,3,1,1]); [ 2, 3, 1, 1, 2, 4, 3, 1, 1 ] gap>

`‣ PermSkewSum` ( perm1, perm2 ) | ( function ) |

Returns: A permutation resulting from `perm1`

\(\ominus\) `perm2`

.

`PermSkewSum`

returns the permutation corresponding to `perm1`

\(\ominus\) `perm2`

if `perm1`

and `perm2`

are both not rank encoded. If both `perm1`

and `perm2`

are rank encoded, then `PermSkewSum`

returns a rank encoded sequence.

gap> PermSkewSum([2,4,1,3],[2,5,4,1,3]); [ 7, 9, 6, 8, 2, 5, 4, 1, 3 ] gap> PermSkewSum([2,3,1,1],[2,4,3,1,1]); [ 7, 8, 6, 6, 2, 4, 3, 1, 1 ] gap>

generated by GAPDoc2HTML