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)