Fifty Shades of J/Chapter 30
Table of Contents ... Glossary ... Previous Chapter ... Next Chapter
(…C&A are a major international clothing retail chain-store. Their last shop closed in England in 2001 –ed).
Principal Topics
- A. (anagram index / anagram) C. (cycle direct / permute) i. (index of) a. (alphabet) ! (factorial), permutations, derangements, dihedral group, alternating group, parity.
A permutation shuffles items within a list. It can be described in two ways, either (1) by what is done in the course of the shuffle, or (2) as a display of its end result. Monadic C. transforms either of these descriptions into the other. Type (1) is always boxed so <7 3 4 is interpreted as “item 7 is replaced by item 3 which is replaced by item 4 which is replaced by item 7”. The occurrence of ‘item 7’ at both the beginning and end of that description show that it is a cycle, and a general permutation is made up of several cycles which do not overlap. The result of carrying out such a series of actions is the image of the permutation, which unfortunately is also popularly referred to as a permutation.
Group-theorists call the items to be permuted the points. Denote by n the number of points. This is called the degree of the permutation. It is not to be confused with the "order" of the abstract group G generated by such a permutation, or set of permutations on the same points, i.e. the cardinality of G. If n=3, then <2 1 0 (type-(1) definition) is a permutation whose image is 2 0 1 (type-(2) definition). If n=4 the image of the same type-(1) permutation is 2 0 1 3, that is the image depends on the degree of a permutation.
Images can be used as indexes to permute general objects using From ({), for example
2 0 1{‘ABC’
CAB
Permutations are in general products of disjoint cycles, and, as stated above monadic C. acts as a toggle between the two types of description
C.2 0;1 3 2 3 0 1 C.2 3 0 1 ┌───┬───┐ │2 0│3 1│ └───┴───┘
The one-to-one correspondence between cycles and images is guaranteed by making the highest index leftmost within each cycle and ordering the cycles in increasing value of leftmost elements. Thus the permutation 1 3;2 0 is identical to 2 0;3 1, although the latter is the preferred choice of representation.
The dyadic form of C. is called Permute, and is very useful in shuffling items within lists, as in
]ten=.(65+i.10){a.
ABCDEFGHIJ
(4 3;7 1)C. ten
AHCEDFGBIJ
When C. is used monadically it is assumed that the degree of the permutation is the maximum integer which appears explicitly in the argument
C.4 3;7 1 NB. points 8 and 9 (both >7) are left fixed in place
0 7 2 4 3 5 6 1
(C.4 3;7 1){ten NB. hence points 8=I and 9=J are dropped from the image
AHCEDFGB
Now consider the dyadic form of the verb A. which is called Anagram. It allows all permutation to be listed in increasing degree
(i.!3) A. i.3 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0
Replacing each permutation image by its ordinal number reduces it to an ink of this as an atom. Let us call this atom the atomic number or A# of the given permutation. If the degree of n is large the A# can be a useful shorthand, so that for example the atomic number A.3 2 1 0 (the final permutation of degree 4 in numerical sequence) is 23.
Permutation-image numbering depends on the degree n, so that the reverse process, that is moving from A# to image provides an obvious niche for dyadic A.
23 A.i.4 3 2 1 0
A more general way of looking at the dyadic form of A. is to view its left argument (x) as the A# of the permutation which is to be applied to the smallest applicable sub-list at the right-hand end of the right argument (y). Thus, for x=1, (1 A.y) shuffles the last two items of list y; x=2 through x=5 shuffle the last three items; 6 through 23 shuffle the last four items; and so on.
Permutations can be combined under ({) ("group-multiplication") in the sense that 1 2 0 (A#=3) multiplied by 1 0 2 (A#=2) yields 0 2 1 (A#=1). Dyadic A. gives us a way of multiplying two group elements represented by their A#s instead of their permutation-images
t=: i.3
(3 A.t) { (2 A.t)
0 2 1
A. (3 A.t) { (2 A.t)
1
Generalising this into a function and table
Verb perm3 multiplies group elements x and y represented by their A#s, getting the result as an A#
perm3=: dyad : 'A.(x A.t){y A.t=.i.3'
3 perm3 2 NB. multiply group-element (A#=3) by (A#=2)
1
Here is the group-multiplication table (the Cayley Table) of the first six A#s
>perm3&>/~ i.6 0 1 2 3 4 5 1 0 3 2 5 4 2 4 0 5 1 3 3 5 1 4 0 2 4 2 5 0 3 1 5 3 4 1 2 0
This is the Cayley Table of the Dihedral Group D3 (see Essay #26: Working in Groups) which is most commonly observed in the symmetries of the equilateral triangle. 0, 3 and 4 correspond to rotations of 0, π/3 and 2π/3, and 1 2 and 5 to reflections in the perpendicular bisectors of the sides.
Within D3 the subgroup formed by 0, 3 and 4 is the cyclic group C3. We can see its Cayley Table embedded in that of D3 above, by blotting out all rows and columns except those belonging to 0, 3 and 4
0 1 2 3 4 5 1 . . . . . 2 . . . . . 3 . . 4 0 . 4 . . 0 3 . 5 . . . . .
in fact all subgroups of D3 are revealed by their elements forming closed sub-tables of D3's Cayley Table.
A more general verb for multiplying group-elements as A#s rather than permutation-images is
perms=: dyad : 'A.(({.x) A.t){,(}.x)A.t=.i.y'
11 5 perms 4
21
where x is the pair of group-elements to be multiplied, and y is the degree of the corresponding permutations, i.e. the (smallest) number of points to be permuted.
This shows, for permutations of degree y=4, multiplying elements 11 and 5 gives element 21. Or, multiplying their corresponding permutation-images (from the table below)
1 3 2 0 { 0 3 2 1
3 1 2 0
Inverses : getting back to where you started
The image permutation whose operation restores the natural numerical ordering of an image permutation p is given by /:p . It is called the inverse of p .
So if the characters in (ten) appear in the order ICEDHFBAJG the instruction to restore them to natural order is
C. /: ten i.'ICEDHFBAJG' ┌─┬─┬───────────────┐ │3│5│9 8 0 7 4 2 1 6│ └─┴─┴───────────────┘
This operational permutation says: keep the fourth and sixth characters (i.e. D and F with indices 3 and 5) fixed in place, the character in the ninth position (J) moves to the tenth, the character in the eighth position (A) moves to the first, and so on.
C.C. /: ten i.t=.'ICEDHFBAJG'
7 6 1 3 2 5 9 4 0 8
(C.C. /: ten i.t){t
ABCDEFGHIJ
A permutation consisting only of 2-cycles is self-inverse. For n=4 there are 10 of these, one containing no 2-cycles, 6 containing a single 2-cycle corresponding to the 6 ways in which a pair of items can be chosen from 4, and 3 containing two pairs of 2-cycles, viz. 3 2;1 0, 3 1;2 0 and 3 0;2 1. There are 8 permutations with 3-cycles which form 4 mutually inverse pairs such as <3 0 2 and <3 2 0, and finally the number of 4-cycles is 6, since a 4-cycle must have 3 as its first item and there are 6 ways in which the remaining 3 items can be permuted.
Permutations possess parity, i.e. they can be classified as odd or even according to whether they are obtainable as the result of an odd or an even number of transpositions (successive two-item swaps) from (i.n). For example
0 1 2 3
. .
--> 0 1 3 2
. .
--> 3 1 0 2
hence 3 1 0 2 is the image of an even permutation.
The table below classifies the permutations of degree 4. In the properties column, O means Odd, S means self-inverse, and D indicates a derangement, that is a permutation in which every item has moved from its home position. The first 6 permutations have 0 in their first position, the next 6 have 1, and so on. However, apart from this labeling by A., number ordering does not reflect group structure. Subgroups of order 2 can be formed by combining 0 with any of the 9 non-identity self-inverse permutations.
The following sets (of A#s) form subgroups of orders 4, 8 and 12 thus
Order 4: {0,7,16,23} {0,2,21,23} (0,1,6,7} {0,5,14,16}
Order 8: {0,7,16,23,6,1,17,22} {0,7,16,23,14,9,5,18]
Order 12: {0,3,4,7,8,11,16,12,15,23,19,20}
of which the last is the set of even permutations, called the Alternating Group of degree 5 (A5)
A# Image Permutation Properties Inverse 0 0 1 2 3 S 1 0 1 3 2 <3 2 O S 2 0 2 1 3 <2 1 O S 3 0 2 3 1 <3 1 2 4 4 0 3 1 2 <3 2 1 3 5 0 3 2 1 <3 1 O S 6 1 0 2 3 <1 0 O S 7 1 0 3 2 3 2;1 0 S D 8 1 2 0 3 <2 0 1 12 9 1 2 3 0 <3 0 1 2 O D 18 10 1 3 0 2 <3 2 0 1 O D 13 11 1 3 2 0 <3 0 1 19 12 2 0 1 3 <2 1 0 8 13 2 0 3 1 <3 1 0 2 O D 10 14 2 1 0 3 <2 0 O S 15 2 1 3 0 <3 0 2 20 16 2 3 0 1 3 1;2 0 S D 17 2 3 1 0 <3 0 2 1 O D 22 18 3 0 1 2 <3 2 1 0 O D 9 19 3 0 2 1 <3 1 0 11 20 3 1 0 2 <3 2 0 15 21 3 1 2 0 <3 0 O S 22 3 2 0 1 <3 1 2 0 O D 17 23 3 2 1 0 3 0;2 1 S D
Code Summary
For permutations described by their anagram numbers (A#s)
perm3=: dyad : 'A.(x A.t){y A.t=:i.3' NB. application of 3-perms x then y
perms=: dyad : 'A.(({.x) A.t){,(}.x)A.t=:i.y' NB. application of y-perms 0{x then 1{x