# 7A. Permutations

Any re-ordering or permutation of the integers i.n is called a permutation vector of order n. If p is a permutation vector, then p&{ is the corresponding permutation function. For example:

```   p=: 4 5 2 1 0 3
text=: 'ABCDEF'
p { text

p&{ text
```

The phrase k=: A. p gives the index of the permutation vector p in the ordered list of !n permutation vectors of order n, and the function k&A. is the corresponding permutation function. For example:

```   ]k=: A. p
590

k A. text

(i.!3) A. i. 3
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
```

The phrase c=: C. p gives the (boxed) cycle representation of p, and either p&C. or c&C. provide the corresponding permutation function. For example:

```   ]c=: C. p
+-+---+-----+
|2|4 0|5 3 1|
+-+---+-----+

c C. text
```

In the phrases p C. x and c C. x, the order of the permutation is determined by the number of items in x, and abbreviated vectors p and c may therefore be used unambiguously:

```   3 1 C. text         NB. Move items to tail
ACEFDB

(<3 1) C. text      NB. Interchange items

(<3 1 4) C. text    NB. Rotate items
AECBDF
```

The application of C. to any abbreviated representation produces the standard form, and two applications of C. therefore provide the standard form for any representation. For example:

```   C. 3 1
+-+-----+
|0|3 1 2|
+-+-----+

C. C. 3 1
0 2 3 1

C. C. <3 1
+-+-+---+
|0|2|3 1|
+-+-+---+

C. C. <3 1 4
+-+-+-----+
|0|2|4 3 1|
+-+-+-----+
```
 m0 =: /: Inverse permutation vector m1 =: /:&.C. Inverse cycle m2 =: (-: >) :: 0: Not-a-box test m3 =: m1`m0 @. m2 Inverse permutation m4 =: C.^:2 Put permutation into standard form m5 =: (<0 _1)&C. Interchange first and last items m6 =: _1&A. Reverse m7 =: 3&A. Rotate last three to the left m8 =: 4&A. Rotate last three right d9 =: ([: +/[:![:}.[:i.[) A. ] Rotate last x to the left d10=: (!@[ - !@<:@[) A. ] Rotate last x to the right m11 =: /:~ Sort up m12 =: \:~ Sort down m13 =: ?~ Random permutation of order y m14=: /:@:?@\$~ Random permutation of order y m15=: ?@! A. i. Random permutation of order y d16=: A. i. x-th permutation of order y m17=: all=: i.@! A. i. All permutations of order y m18=: ,:@i.`([: ,/ 0&,.@ (\$:&.<:){"2 1 \:"1@=@i.)@.(1&<) All permutations of order y (recursive definition) m19=: pow=: {^:(]`(i.@#@[)) Permutation x to the power y m20=: [: {/ ] \$ ,:@[ Permutation x to the power y m21=: i.@#@[C.~(#&>@C.@[| ])#C.@[ Permutation x to the power y m22=: pow 2&^ Permutation x to the power 2^y m23=: 3 : (':'; '{~^:y x') Permutation x to the power 2^y m24=: {~@]^:(]`[) Permutation x to the power 2^y m25=: ord=: *./@(#&>"_)@C. The order of a permutation m26=: sg=: pow i.@ord Subgroup generated by permutation y m27=: [: {/\ ord \$ ,: " m28=: ~.@(,/)@({"1/~)^:_@(i.@{:@\$ ,: ]) " § 4.4 Hui  d29=: \:@[{] Move items located by x to front of y m30=: 1: |. ] Rotate y by 1 to the left (or up) d31=: !@[ * ! Number of perms of y objects x at a time m32=: (] {~ [: /: ] = ' '"_)"1 Move all blanks to end of row d33=: /:@[ { ] Move items located by x to end of y m34=: _1: |. ] Rotate y by 1 to the right (or down) m35=: ~.@(,/)@({"1/~)^:_@(i.@{:@\$,]) Subgroup generated by a matrix of permutations m36=: {"1/~ The group table of a matrix of permutations m37=: ugt=: ~.@(,/)@({"1/~) The unique elements of the permutation group m38=: pbi=: i.@{:@\$ , ] Preface a matrix of permutations by the identity m39=: ugt^:_ @ pbi The subgroup generated by a matrix of permutations (same as m35)