Help / Phrases / 7. A. Permutations
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help Phrases
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) |