JPhrases/Permutations

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
EFCBAD

   p&{ text
EFCBAD

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
EFCBAD

   (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
EFCBAD

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
ADCBEF

   (<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 [4]
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)