A. Permutations

>> << Ndx Usr Pri Phr Dic Rel Voc !: 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)

>> << Ndx Usr Pri Phr Dic Rel Voc !: wd Help Phrases