chap8.txt

  
  8 Properties of Permutations
  
  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 σ is a set of contiguous values which in σ have
  consecutive indices.
  
  A permutation of length n is called simple if it only contains the intervals
  of length 0, 1 and n.
  
  
  8.1 Intervals in Permutations
  
  As  mentioned  above,  an interval of a permutation σ is a set of contiguous
  numbers  which in σ have consecutive indices. For example in σ = 4 6 8 7 1 5
  2 3 the following is an interval σ(2)σ(3)σ(4)=6 8 7 whereas σ(4)σ(5)σ(6)=7 1
  5 is not.
  
  8.1-1 IsInterval
  
  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.
  
    Example  
    gap> IsInterval([3,6,9,2]);
    false
    gap> IsInterval([2,6,5,3,4]);
    true
    gap>  
  
  
  
  8.2 Simplicity
  
  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.
  
  8.2-1 IsSimplePerm
  
  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 [8] to
  compare the perm against the identity permutation of the same length.
  
    Example  
    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> 
  
  
  
  8.3 Point Deletion in Simple Permutations
  
  In [7] 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.
  
  8.3-1 OnePointDelete
  
  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.
  
    Example  
    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> 
  
  
  8.3-2 TwoPointDelete
  
  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.
  
    Example  
    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> 
  
  
  8.3-3 PointDeletion
  
  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.
  
    Example  
    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> 
  
  
  
  8.4 Block-Decomposition
  
  Given  a permutation π of length m and nonempty permutations α_1,...,α_m the
  inflation of π by α_1,...,α_m, written as π[α_1,...,α_m], is the permutation
  obtained  by  replacing  each  entry  π(i)  by  an  interval  that  is order
  isomorphic  to  α_i  [4].  Conversely  a  block-decomposition  of  σ  is any
  expression of σ as an inflation σ=π[α_1,...,α_m]. The block decomposition of
  a  permutation  is unique if and only if σ,π,α_1,...,α_n all are in the same
  pattern class and π is simple and π≠ 1 2, 2 1 [1].
  
  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]].
  
  8.4-1 Inflation
  
  Inflation( list_of_perms )  function
  Returns:  A  permutation  that  represents  the  inflation  of  the  list of
            permutations,  taking  the first permutation to be π, 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.
  
    Example  
    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> 
  
  
  8.4-2 BlockDecomposition
  
  BlockDecomposition( perm )  function
  Returns:  A  list  of  permutations, representing the block-decomposition of
            perm.  In the list the first permutation is π, 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.
  
    Example  
    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>  
  
  
  
  8.5 Plus-Decomposability
  
  A  permutation  σ  is  said  to  be  plus-decomposable  if it can be written
  uniquely in the following form,
  
  
  σ = 12 [α_1,α_2]
  
  where α_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.
  
  8.5-1 IsPlusDecomposable
  
  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.
  
    Example  
    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> 
  
  
  
  8.6 Minus-Decomposability
  
  Minus-decomposability  is  essentially the same as plus-decomposability, the
  difference  is  that  if  a  permutation  σ is minus-decomposable, it can be
  written uniquely in the following form,
  
  
  σ = 21 [α_1,α_2]
  
  where α_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.
  
  8.6-1 IsMinusDecomposable
  
  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 ≤ x.
  
    Example  
    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> 
  
  
  
  8.7 Sums of Permutations
  
  The  direct sum of two permutations σ=σ_1 ... σ_k and τ=τ_1...τ_l is defined
  as,
  
  
  σ ⊕ τ = σ_1 σ_2...σ_k τ_1+k τ_2+k...τ_l+k .
  
  In a similar fashion the skew sum of σ, τ is
  
  
  σ ⊖ τ = σ_1+l σ_2+l...σ_k+l τ_1 τ_2...τ_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 σ,τ represented as their rank
  encoded sequences is the permutation which has the rank encoding that is the
  concatention  of  the  rank  encoding  of  σ  and  τ.  The  skew  sum of two
  permutations  σ,τ  encoded  by the rank encoding is the concatenation of the
  rank encodings of σ and τ where in the sequence corresponding to σ under the
  rank  encoding each element has been increased by l, with l being the length
  of τ.
  
  8.7-1 PermDirectSum
  
  PermDirectSum( perm1, perm2 )  function
  Returns:  A permutation resulting from perm1 ⊕ perm2.
  
  PermDirectSum  returns  the  permutation  corresponding  to perm1 ⊕ 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.
  
    Example  
    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> 
  
  
  8.7-2 PermSkewSum
  
  PermSkewSum( perm1, perm2 )  function
  Returns:  A permutation resulting from perm1 ⊖ perm2.
  
  PermSkewSum  returns the permutation corresponding to perm1 ⊖ 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.
  
    Example  
    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>