Vocabulary/ccapdot
>> << Back to: Vocabulary Thru to: Dictionary
C. y Cycle-Direct
Rank 1 -- operates on lists of y, producing a list of variable length for each one -- WHY IS THIS IMPORTANT?
Converts the permutation y between direct and cycle representations.
]cycle =: C. 1 2 0 5 4 3 NB. Convert to cycle form +-----+-+---+ |2 0 1|4|5 3| +-----+-+---+ C. cycle NB. Convert back to direct form 1 2 0 5 4 3
A permutation of an array a is an array b containing the same items as a but possibly in a different order. The relation between the ordering of the items of a and b is called a permutation, and the action of creating b from a is called applying the permutation to a.
The direct representation, d, of a permutation, lists for each index i in b the index in a that moved to position i. In the example above, item 1 in a moves to be item 0 of b, item 2 of a moves to be item 1 of b, item 0 of a to item 2 of b, and so on.
A cycle representation c of a permutation breaks the permutation into cycles where each listed item moves to the position of the next number in the cycle, with the last item in the cycle going to the first position in the cycle. In the example above, the first cycle (2 0 1) indicates that the item in position 2 moves to position 0, the item in position 0 to position 1, and the item in position 1 to position 2. The cycle (5 3) indicates that items 5 and 3 exchange places, and the cycle (4) indicates that item 4 does not move.
Common Uses
1. Find the cycle form of a permutation, as above. In standard math notation the cycles are represented in parentheses, as
1 2 0 5 4 3 <--> (2 0 1)(4)(5 3)
2. Examine the cycle structure of a given permutation p.
The cycle representation reveals many of the properties of p to a group theorist. Moreover the cycle representation is one of the most compact and convenient forms for handling permutations in books and hand-calculations.
More Information
1. The cycle representation of a permutation is not unique: the cycles may be presented in any order and each cycle may start with any of its members.
Cycle representations produced by C. y are put into a canonical form as follows:
- The largest index in each cycle comes first
- The cycles are sorted into ascending order of their largest index
Note that with this canonical form, the cycles can easily be identified even from the raze of the canonical form, as each value higher than all preceding values starts a cycle.
This ordering is expressed in canoncycle below. To use a different canonical form, modify canoncycle.
NB. verb to put a cyclic representation into canonical order
NB. There must be no omitted or negative indexes
canoncycle =: (/: {.@>) @: (,@(|.~ (i. >./))&.>)
]permc =: 6;0 5 1;2 3 4 NB. A cycle form
+-+-----+-----+
|6|0 5 1|2 3 4|
+-+-----+-----+
canoncycle permc NB. canonical form
+-----+-----+-+
|4 2 3|5 1 0|6|
+-----+-----+-+
C. C. permc NB. J produces canonical form
+-----+-----+-+
|4 2 3|5 1 0|6|
+-----+-----+-+
2. The length n of a permutation y is n =. >: >./;y , i.e., one more than the largest value in y. This value must be positive. Any negative index i in y, whether in a box or not, is processed as i+n .
In other words, negative values count back from the end, just like negative array indexing.
C. C. _3 1 2 NB. n = >:2 = 3 0 1 2
3. A completely-described permutation of length n includes each value of i. n exactly once. If some of those values are omitted, default values are assumed.
- for permutations y in direct form, omitted values are prepended to the beginning of y before the conversion to cycle form.
- for permutations y in cycle form, omitted values are assumed to represent cycles of length 1, in other words, positions that are unaffected by the permutation.
To see the complete form of an incomplete permutation, apply C. y twice, which will convert the permutation to canonical form in its original representation:
C. C. 4 2 6 NB. incomplete direct form: omitted values move to front 0 1 3 5 4 2 6 C. C. 1 3;2 5 NB. incomplete cycle form: omitted values do not move +-+---+-+---+ |0|3 1|4|5 2| +-+---+-+---+
4. If, after the conversion of originally negative values, y has duplicate values, or any values less than 0 or greater than or equal to the length n of the permutation, an error is signaled.
Details
1. If y is an empty numeric or character list, an error is signaled. If y is an empty list of boxes, the result is an empty numeric list (i.e. an empty permutation).
C.!.2 y Permutation Parity
Rank 1 -- operates on lists of y, producing a list for each one -- WHY IS THIS IMPORTANT?
Calculates the Levi-Civita symbol (ε) of y:
1 y is a permutation with even parity _1 y is a permutation with odd parity 0 y is not a permutation
C.!.2 (0 1 2 3) NB. Even parity 1 C.!.2 (1 0 2 3) NB. Odd parity _1 C.!.2 (1 0 0 3) NB. Repeated index - not a permutation 0
Common Uses
Parity is an invariant property of a permutation. Even parity means that the permutation can be split into an even number of transpositions (2-cycles), not necessarily disjoint. There will be several distinct ways of doing this, but the number of transpositions will always be even.
z2=: <0 1 NB. a single transposition --> odd parity z2 C. A NB. -applied to 12 points BACDEFGHIJKL C. z2 NB. monadic C. returns a direct permutation, but the shortest possible. 1 0 C.!.2 (C. z2) NB. Compute parity: _1 means Odd parity _1
z3=: (0 1);(2 3) NB. two transpositions --> even parity z3 C. A NB. -applied to 12 points BADCEFGHIJKL C. z3 NB. monadic C. returns a direct permutation 1 0 3 2 C.!.2 (C. z3) NB. Compute parity: 1 means Even parity 1
x C. y Permute
Rank 1 _ -- operates on lists of x and the entirety of y -- WHY IS THIS IMPORTANT?
Applies the permutation x to the items of y.
1 3 0 2 C. 'abcd' NB. Direct form of permutation: same as x { y
bdac
(1 2;3 0) C. 'abcd' NB. cycle form: exchange items 1 & 2, 3 & 0
dcba
Common Uses
1. To apply a permutation given in cycle form.
If the permutation is complete and in direct form, just use x { y.
2. To apply an incomplete permutation (one in which values are missing from x)
(<1 2) C. 'abcde' NB. Cycle form: exchange items 1 & 2, leave others unchanged acbde (2 1) C. 'abcde' NB. Direct form: select items 2 1, put the other items in front adecb
More Information
1. The length n of the permutation is always # y, the number of items of y.
2. Negative values in x are handled as for the monadic case of C. y , except that n is #y.
3. If x is a complete permutation of length #y, that is, if all values of i.#y are in ;x, x C. y is the same as:
4. If x is not complete, it is filled out according to the rules given for the monadic case, except that n is #y. This means that when x is not complete, x C. y is not the same as (C. x) C. y .
Details
1. The shape of the result of x C. y is always the shape of y.
2. if x is an empty list of any type, x C. y is y.