Permutations

Next • Previous • Main

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		Move items to tail
ACEFDB

   (<3 1) C. text		Interchange items
ADCBEF

   (<3 1 4) C. text	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)

Next • Previous • Main