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