GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it

1
  
2
  8 Properties of Permutations
3
  
4
  It  has  been  of interest to the authors to compute different properties of
5
  permutations. Inspections include plus- and minus-decomposable permutations,
6
  block-decompositions  of  permutations,  as  well  as the computation of the
7
  direct  and skew sum of permutations. First a couple of definitions on which
8
  some of the properties are based on:
9
  
10
  An interval of a permutation σ is a set of contiguous values which in σ have
11
  consecutive indices.
12
  
13
  A permutation of length n is called simple if it only contains the intervals
14
  of length 0, 1 and n.
15
  
16
  
17
  8.1 Intervals in Permutations
18
  
19
  As  mentioned  above,  an interval of a permutation σ is a set of contiguous
20
  numbers  which in σ have consecutive indices. For example in σ = 4 6 8 7 1 5
21
  2 3 the following is an interval σ(2)σ(3)σ(4)=6 8 7 whereas σ(4)σ(5)σ(6)=7 1
22
  5 is not.
23
  
24
  8.1-1 IsInterval
25
  
26
  IsInterval( list )  function
27
  Returns:  true, if list is an interval.
28
  
29
  IsInterval  takes  in  any  list  with unique elements, which can be ordered
30
  lexicographically and checkes whether it is an interval.
31
  
32
    Example  
33
    gap> IsInterval([3,6,9,2]);
34
    false
35
    gap> IsInterval([2,6,5,3,4]);
36
    true
37
    gap>  
38
  
39
  
40
  
41
  8.2 Simplicity
42
  
43
  As  mentioned  above  a permutation is said to be simple if it only contains
44
  intervals of length 0, 1 or the length of the permutation.
45
  
46
  8.2-1 IsSimplePerm
47
  
48
  IsSimplePerm( perm )  function
49
  Returns:  true if perm is simple.
50
  
51
  To  check  whether  perm  (length  of  perm  =  n)  is  a simple permutation
52
  IsSimplePerm  uses the basic algorithm proposed by Uno and Yagiura in [8] to
53
  compare the perm against the identity permutation of the same length.
54
  
55
    Example  
56
    gap> IsSimplePerm([2,3,4,5,1,1,1,1]);
57
    true
58
    gap> IsSimplePerm([2,4,6,8,1,3,5,7]);
59
    true
60
    gap> IsSimplePerm([3,2,8,6,7,1,5,4]);
61
    false
62
    gap> 
63
  
64
  
65
  
66
  8.3 Point Deletion in Simple Permutations
67
  
68
  In [7] it is shown how one can get chains of permutations by starting with a
69
  simple permutation and then removing either a single point or two points and
70
  the resulting permutation would still be simple. We have applied this theory
71
  to  create  functions  such  that  the set of simple permutations of shorter
72
  length, by one deletion, can be found.
73
  
74
  8.3-1 OnePointDelete
75
  
76
  OnePointDelete( perm )  function
77
  Returns:  A list of simple permutations with one point less than perm.
78
  
79
  OnePointDelete removes single points in the simple permutation and returns a
80
  list of the resulting simple permutations, in their rank encoding.
81
  
82
    Example  
83
    gap> OnePointDelete([5,2,3,1,2,1]);
84
    [ [ 2, 3, 1, 2, 1 ], [ 4, 1, 2, 2, 1 ] ]
85
    gap> OnePointDelete([5,2,4,1,6,3]);
86
    [ [ 2, 3, 1, 2, 1 ], [ 4, 1, 2, 2, 1 ] ]
87
    gap> 
88
  
89
  
90
  8.3-2 TwoPointDelete
91
  
92
  TwoPointDelete( perm )  function
93
  Returns:  The exceptional permutation with two point less than perm.
94
  
95
  TwoPointDelete  removes  two points of the input exceptional permutation and
96
  returns the list of the unique resulting permutation, in its rank encoding.
97
  
98
    Example  
99
    gap> TwoPointDelete([2,4,6,8,1,3,5,7]);
100
    [ [ 2, 3, 4, 1, 1, 1 ] ]
101
    gap> TwoPointDelete([2,3,4,5,1,1,1,1]);
102
    [ [ 2, 3, 4, 1, 1, 1 ] ]
103
    gap> 
104
  
105
  
106
  8.3-3 PointDeletion
107
  
108
  PointDeletion( perm )  function
109
  Returns:  A list of simple permutations with of shorter length than perm.
110
  
111
  PointDeletion   takes   any  simple  permutation  does  not  matter  whether
112
  exceptional or not and removes the right number of points.
113
  
114
    Example  
115
    gap> PointDeletion([5,2,3,1,2,1]);
116
    [ [ 2, 3, 1, 2, 1 ], [ 4, 1, 2, 2, 1 ] ]
117
    gap> PointDeletion([5,2,4,1,6,3]);
118
    [ [ 2, 3, 1, 2, 1 ], [ 4, 1, 2, 2, 1 ] ]
119
    gap> PointDeletion([2,4,6,8,1,3,5,7]);
120
    [ [ 2, 3, 4, 1, 1, 1 ] ]
121
    gap> PointDeletion([2,3,4,5,1,1,1,1]);
122
    [ [ 2, 3, 4, 1, 1, 1 ] ]
123
    gap> 
124
  
125
  
126
  
127
  8.4 Block-Decomposition
128
  
129
  Given  a permutation π of length m and nonempty permutations α_1,...,α_m the
130
  inflation of π by α_1,...,α_m, written as π[α_1,...,α_m], is the permutation
131
  obtained  by  replacing  each  entry  π(i)  by  an  interval  that  is order
132
  isomorphic  to  α_i  [4].  Conversely  a  block-decomposition  of  σ  is any
133
  expression of σ as an inflation σ=π[α_1,...,α_m]. The block decomposition of
134
  a  permutation  is unique if and only if σ,π,α_1,...,α_n all are in the same
135
  pattern class and π is simple and π≠ 1 2, 2 1 [1].
136
  
137
  For example the inflation of 25413[21,1,1,1,2413]=3 2 8 9 1 5 7 4 6, written
138
  in GAP this is [[2,5,4,1,3],[2,1],[1],[1],[1],[2,4,1,3]]. This decomposition
139
  of  3  2  8  9  1  5 7 4 6 is not unique. The unique block-decomposition, as
140
  described above, for 3 2 8 9 1 5 7 4 6=2413[21,12,1,2413] or in GAP notation
141
  [3,2,8,9,1,5,7,4,6]=[[2,4,1,3],[2,1],[1,2],[1],[2,4,1,3]].
142
  
143
  8.4-1 Inflation
144
  
145
  Inflation( list_of_perms )  function
146
  Returns:  A  permutation  that  represents  the  inflation  of  the  list of
147
            permutations,  taking  the first permutation to be π, as described
148
            in the definition of inflation.
149
  
150
  Inflation  takes the list of permutations that stand for a box decomposition
151
  of  a permutation, and calculates that permutation by replacing each entry i
152
  in  the first permutation by an interval order isomorphic to the permutation
153
  in index i+1.
154
  
155
    Example  
156
    gap> Inflation([[3,2,1],[1],[1,2],[1,2,3]]);
157
    [ 6, 4, 5, 1, 2, 3 ]
158
    gap> Inflation([[1,2],[1],[4,2,1,3]]);
159
    [ 1, 5, 3, 2, 4 ]
160
    gap> Inflation([[2,4,1,3],[2,1],[3,1,2],[1],[2,4,1,3]]);
161
    [ 3, 2, 10, 8, 9, 1, 5, 7, 4, 6 ]
162
    gap> 
163
  
164
  
165
  8.4-2 BlockDecomposition
166
  
167
  BlockDecomposition( perm )  function
168
  Returns:  A  list  of  permutations, representing the block-decomposition of
169
            perm.  In the list the first permutation is π, as described in the
170
            definiton of block-decomposition above.
171
  
172
  BlockDecomposition  takes  a  plus- and minus-indecomposable permutation and
173
  decomposes  it into its maximal maximal intervals, which are preceded by the
174
  simple  permutation  that  represents  the  positions of the intervals. If a
175
  plus-  or  minus-decomposable  permutation  is input, then the decomposition
176
  will  not  be the unique decomposition, by the definition of plus- or minus-
177
  decomposable permutations, see below.
178
  
179
    Example  
180
    gap> BlockDecomposition([3,2,10,8,9,1,5,7,4,6]);
181
    [ [ 2, 4, 1, 3 ], [ 2, 1 ], [ 3, 1, 2 ], [ 1 ], [ 2, 4, 1, 3 ] ]
182
    gap> BlockDecomposition([1,2,3,4,5]);                      
183
    [ [ 1, 2 ], [ 1, 2, 3, 4 ], [ 1 ] ]
184
    gap> BlockDecomposition([5,4,3,2,1]);
185
    [ [ 2, 1 ], [ 4, 3, 2, 1 ], [ 1 ] ]
186
    gap>  
187
  
188
  
189
  
190
  8.5 Plus-Decomposability
191
  
192
  A  permutation  σ  is  said  to  be  plus-decomposable  if it can be written
193
  uniquely in the following form,
194
  
195
  
196
  σ = 12 [α_1,α_2]
197
  
198
  where α_1 is not plus-decomposable.
199
  
200
  The  subset  of  a  rational  class,  containing  all  permutations that are
201
  plus-decomposable and in the class, has been found to be also rational under
202
  the rank encoding.
203
  
204
  8.5-1 IsPlusDecomposable
205
  
206
  IsPlusDecomposable( perm )  function
207
  Returns:  true if perm is plus-decomposable.
208
  
209
  To  check whether perm is a plus-decomposable permutation IsPlusDecomposable
210
  uses  the  fact that there has to be an interval 1..x where x <n (n = length
211
  of the perm) in the rank encoded permutation that is a valid rank encoding.
212
  
213
    Example  
214
    gap> IsPlusDecomposable([3,3,2,3,2,2,1,1]);
215
    true
216
    gap> IsPlusDecomposable([3,4,2,6,5,7,1,8]);
217
    true
218
    gap> IsPlusDecomposable([3,2,8,6,7,1,5,4]);
219
    false
220
    gap> 
221
  
222
  
223
  
224
  8.6 Minus-Decomposability
225
  
226
  Minus-decomposability  is  essentially the same as plus-decomposability, the
227
  difference  is  that  if  a  permutation  σ is minus-decomposable, it can be
228
  written uniquely in the following form,
229
  
230
  
231
  σ = 21 [α_1,α_2]
232
  
233
  where α_1 is not minus-decomposable.
234
  
235
  Here  also, the subset of a rational class, containing all permutations that
236
  are minus-decomposable and in the class, has been found to be rational under
237
  the rank encoding.
238
  
239
  8.6-1 IsMinusDecomposable
240
  
241
  IsMinusDecomposable( perm )  function
242
  Returns:  true if perm is minus-decomposable.
243
  
244
  To  check  whether  perm  (length  of  perm  =  n)  is  a minus-decomposable
245
  permutation IsMinusDecomposable uses the fact that the first n-x, where x<n,
246
  letters in the rank encoding of perm have to be >x and that the letters from
247
  position x+1 until the last one have to be ≤ x.
248
  
249
    Example  
250
    gap> IsMinusDecomposable([3,3,3,3,3,3,2,1]);
251
    true
252
    gap> IsMinusDecomposable([3,4,5,6,7,8,2,1]);
253
    true
254
    gap> IsMinusDecomposable([3,2,8,6,7,1,5,4]);
255
    false
256
    gap> 
257
  
258
  
259
  
260
  8.7 Sums of Permutations
261
  
262
  The  direct sum of two permutations σ=σ_1 ... σ_k and τ=τ_1...τ_l is defined
263
  as,
264
  
265
  
266
  σ ⊕ τ = σ_1 σ_2...σ_k τ_1+k τ_2+k...τ_l+k .
267
  
268
  In a similar fashion the skew sum of σ, τ is
269
  
270
  
271
  σ ⊖ τ = σ_1+l σ_2+l...σ_k+l τ_1 τ_2...τ_l .
272
  
273
  The  calculation  of the direct and skew sums of permutations using the rank
274
  encoding  is  also  straight  forward and is used in the functions described
275
  below.  The  direct  sum  of  two permutations σ,τ represented as their rank
276
  encoded sequences is the permutation which has the rank encoding that is the
277
  concatention  of  the  rank  encoding  of  σ  and  τ.  The  skew  sum of two
278
  permutations  σ,τ  encoded  by the rank encoding is the concatenation of the
279
  rank encodings of σ and τ where in the sequence corresponding to σ under the
280
  rank  encoding each element has been increased by l, with l being the length
281
  of τ.
282
  
283
  8.7-1 PermDirectSum
284
  
285
  PermDirectSum( perm1, perm2 )  function
286
  Returns:  A permutation resulting from perm1 ⊕ perm2.
287
  
288
  PermDirectSum  returns  the  permutation  corresponding  to perm1 ⊕ perm2 if
289
  perm1  and perm2 are both not rank encoded. If both perm1 and perm2 are rank
290
  encoded, then PermDirectSum returns a rank encoded sequence.
291
  
292
    Example  
293
    gap> PermDirectSum([2,4,1,3],[2,5,4,1,3]);
294
    [ 2, 4, 1, 3, 6, 9, 8, 5, 7 ]
295
    gap> PermDirectSum([2,3,1,1],[2,4,3,1,1]);
296
    [ 2, 3, 1, 1, 2, 4, 3, 1, 1 ]
297
    gap> 
298
  
299
  
300
  8.7-2 PermSkewSum
301
  
302
  PermSkewSum( perm1, perm2 )  function
303
  Returns:  A permutation resulting from perm1 ⊖ perm2.
304
  
305
  PermSkewSum  returns the permutation corresponding to perm1 ⊖ perm2 if perm1
306
  and  perm2  are  both  not  rank  encoded.  If both perm1 and perm2 are rank
307
  encoded, then PermSkewSum returns a rank encoded sequence.
308
  
309
    Example  
310
    gap> PermSkewSum([2,4,1,3],[2,5,4,1,3]);
311
    [ 7, 9, 6, 8, 2, 5, 4, 1, 3 ]
312
    gap> PermSkewSum([2,3,1,1],[2,4,3,1,1]);
313
    [ 7, 8, 6, 6, 2, 4, 3, 1, 1 ]
314
    gap> 
315
  
316
  
317

318