| Cycle | C. 1 1 _ | Permute |
|
C.p yields a list of boxed lists of the atoms
of i.#p, called the standard cycle
representation of the permutation p . Thus,
if p=:4 5 2 1 0 3,
then C.p is (,2);4 0;5 3 1
because the permutation p moves to
position 2 the item 2,
to 4 the item 0,
to 0 the item 4,
to 5 the item 3,
to 3 the item 1, and
to 1 the item 5. The monad C.
is self-inverse; applied to a standard cycle it gives the
corresponding direct representation. A given permutation could be represented by cycles in a variety of ways; the standard form is made unique by the following restrictions: the cycles are disjoint and exhaustive (i.e., the atoms of the boxed elements together form a permutation vector); each boxed cycle is rotated to begin with its largest element; and the boxed cycles are put in ascending order on their leading elements. C. is extended to non-negative non-standard cases by treating any argument q as a representation of a permutation of order 1+>./; q . The monad C.!.2 computes the parity of a permutation p ; it is 1 or _1 as the number is even or odd of pairwise interchanges necessary to get p from the identity permutation i.#p (and 0 if p is not a permutation). For example: ] x=: 2 , (i.4) ,: 1 0 2 3 2 2 2 2 0 1 2 3 1 0 2 3 C.!.2 x 0 1 _1 |
If p and c are standard and cycle representations
of order #b, then p C. b and c C. b produce
the permutation of b . The arguments p and c
can be non-standard in ways to be defined. In particular,
negative integers down to -#b may be used, and are treated
as their residues modulo #b . If q is not boxed, and the elements of (#b)|q are distinct, then q C. b is equivalent to p{b , where p is the standard form of q that is given by p=:((i.n)-.n|q),n|q , for n=:#b . In other words, positions occurring in q are moved to the tail end. If q is boxed, the elements of (#b)|>j{q must be distinct for each j , and the boxes are applied in succession. For example:
(2 1;3 0 1) C. i.5
1 2 3 0 4
(<2 1) C. (<3 0 1) C. i.5
1 2 3 0 4
q=: C. p=: 1 2 3 0 4 [ a=: 'abcde'
q ; (q C. a) ; (p C. a) ; (p { a)
+-----------+-----+-----+-----+
|+-------+-+|bcdae|bcdae|bcdae|
||3 0 1 2|4|| | | |
|+-------+-+| | | |
+-----------+-----+-----+-----+
a ; (<0 _1) C. a
+-----+-----+
|abcde|ebcda|
+-----+-----+
|
] p=: 22 ?. 22 NB. A random permutation of order 22
16 18 21 8 6 15 10 14 7 11 0 2 5 3 9 12 20 17 4 19 13 1
C. p NB. Its cycles
+-------+--+--+-----------------------------------------+
|15 12 5|17|19|21 1 18 4 6 10 0 16 20 13 3 8 7 14 9 11 2|
+-------+--+--+-----------------------------------------+
*./ #&> C. p NB. LCM of the cycle lengths
51
# ~. p&{^:(i.200) i.#p NB. Size of the subgroup generated by p
51
The verb CT computes the complete tensor of order n
as a sparse array; entry (<i){CT n is the parity
of the index i .
CT=: 3 : '(C.!.2 p) (<"1 p=. (i.!y) A. i.y)}1$.$~y'
CT 3
0 1 2 | 1
0 2 1 | _1
1 0 2 | _1
1 2 0 | 1
2 0 1 | 1
2 1 0 | _1
($.^:_1 CT 3) ; ,"2 ' ' ,"1 '012'{~ >{ i.&.> $~3
+--------+------------+
| 0 0 0| 000 001 002|
| 0 0 1| 010 011 012|
| 0 _1 0| 020 021 022|
| | |
| 0 0 _1| 100 101 102|
| 0 0 0| 110 111 112|
| 1 0 0| 120 121 122|
| | |
| 0 1 0| 200 201 202|
|_1 0 0| 210 211 212|
| 0 0 0| 220 221 222|
+--------+------------+
(CT 3) -: C.!.2&> { i.&.> $~ 3
1
] m=: ?. 3 3$10
6 5 9
2 4 9
0 7 0
+/ , (CT #m) * *// m
_252
-/ .* m NB. Determinant
_252