J-ottings 23: Just what do they sell at C. and A.?

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 39

Are you the sort of person who shuffles things around, papers on your desk, people in your department and so on? If so, read on, this is for you. A permutation is just a shuffle of items within an object. It can be described in two ways, either as what you do in the course of the shuffle (e.g. switch items four, five and two around cyclically, and also items one and three), or as a display of the end result (e.g. items finish in order three, four, one, five, two). The former type of description, that is of the operation, is logically prior to the latter. Any permutation is describable as a product of non-overlapping cycles (see the following paragraph for what this means), whereas the end result is the vector of positions which results from the execution of these cycles.

In J, the verb C. transforms either of these two descriptions into the other. The first kind is always boxed which can be ensured by using either of the "box" or "link" verbs. For example, <7 3 6 4 should be interpreted as

"item 7 is replaced by item 3 which is replaced by item 6 which is replaced by item 4 which is replaced by item 7",

in other words think of "is replaced by item" as being inserted in the gaps in a cycle vector as in the initial preparation for evaluating "function insert".

The C. verb thus forces an explicit distinction between a permutation in the operational sense, that is a set of non-overlapping cycles, and the image of such a permutation, which unfortunately is also popularly referred to as a permutation. Denote by n the number of items available to be permuted (this is called the order of the permutation). If n = 3, then, using the definitions just given, <2 1 0 is a permutation whose image is 2 0 1. If n = 4 the image of the same permutation is 2 0 1 3. In other words the image of an operational permutation depends on its order. Images can be used as indexes, for example with the "from" verb as in 2 0 1 {'ABC' which evaluates to 'CAB'.

Permutations are in general products of disjoint cycles so that a cycle 2 0;3 1 has as its image C.2 0;1 3 which is 2 3 0 1, and conversely the cycle representation of 2 3 0 1 is C.2 3 0 1 which is 2 0;3 1. The one-to-one correspondence between cycles and images can be guaranteed (and is so guaranteed in J) 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, which is how it is best to think about it, although C. 1 3;2 0 evaluates correctly to 2 3 0 1.

The dyadic form of C., which is called "from direct", is very useful for shuffling items within objects. For example, if ten items in an object, which could be either upper-case letters (say ten=.(65+i.10){a.), or rows of a character matrix, represent ten people, and it is desired to switch the fourth and fifth, and also the second and eighth, use

   (4 3;7 1)C.ten
AHCEDFGBIJ

The left argument can be either a permutation or a permutation image, and it is applied directly to the items of the right argument.

There is an important distinction between "from direct" and explicit "from". This is demonstrated by

   (C.4 3;7 1){ten
AHCEDFGB

Now consider A. which is a verb called "atomic permute". The force of the word "atomic" is that all the permutation images of i.3 say can be listed in increasing numerical order by

   (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 image by its ordinal number reduces it to an integer from the set i.!3 – think of this as an "atom". If the order n is large this can be a useful shorthand. Monadic A. supplies this shorthand, so that for example A. 3 2 1 0 (the final permutation of order 4 in numerical sequence) is 23. Image numbering depends on the order n, so that the reverse process, that is moving from atomic number 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 as an atomic number identifying a permutation to be applied to the smallest applicable sub-vector at the right hand end of the right argument y.. For example 1 A. y. shuffles the last two items in an object, 2 A. y. through 5 A. y. shuffle the final three items, 6 A. y. through 23 A. y. shuffle the final four items, and so on.

It is easy to construct the algebra of composing successive permutations of a given order as tables of atoms, for example

   each=.&>
   pans3=:3 :0       NB. table of compositions of permutations of
:                    NB. order 3 in sequence by atomic number
A.(x.A.t){y.A.t=.i.3
)
   >pans3  each/~ 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

The leading diagonal has just two non-zero entries, which suggest the cyclic nature of atoms 0, 3 and 4. They form a subgroup (see J-ottings 22) in their own right; reorganising the table, and editing its output shows its fundamental structure:

   >pans3 each/~ 0 3 4 1 2 5
0 3 4   1 2 5
3 4 0   5 1 2
4 0 3   2 5 1

1 2 5   0 3 4
2 5 1   4 0 3
5 1 2   3 4 0

This non-symmetric group is isomorphic to the dihedral group D3 (again see J-ottings 22) which describes the symmetries of the equilateral triangle. 0, 3 and 4 correspond to rotations by 0, π/3 and 2π/3, and 1, 2 and 5 to reflections in the three perpendicular bisectors of the sides. The subgroup formed by (0,3,4) is called the cyclic group C3.

The isomorphism between permutations of order 3 and the symmetries of the equilateral triangle is simple to envisage. The step from order 3 to order 4 however involves a large leap in the size of the underlying groups since there are now 24 permutations and so the group table has 576 entries. The table is obtained by >pans4 each/~ i.24 . (pans4 is the same as pans3 except that ‘3’ is replaced by ‘4’), and an edited subsection of it is given below.

          6  7   8  9  10 11     12 13  14 15  16 17
                 ...                    ...
12       14 20   0 21   1 15      8 22   2 23   3  9
13       15 21   1 20   0 14      9 23   3 22   2  8
14 ..    12 18   2 23   4 17      6 19   0 21   5 11
15       13 19   3 22   5 16      7 18   1 20   4 10
16       17 23   4 18   2 12     11 21   5 19   0  6
17       16 22   5 19   3 13     10 20   4 18   1  7

The full table is like a multiplication table which you would look up to find the effect of applying any two permutations of order 4 in sequence. For example 13 A. 7 A.i.4 has the same permutation image as 21 A.i.4, and permutation 10 has the effect of reversing permutation 13. The table is non-symmetrical as the second six by six block above shows, but it is full of highly intertwined internal symmetries.

Inverses: reshuffling back to where you were¶

The image permutation which restores the natural numerical ordering of the image permutation y. is /:y.. So if the ten people represented by upper case characters ten=.'ABCDEFGHIJ' find themselves in the order ICEDHFBAJG, the operational instructions to restore them to natural order are

   C. /: ten i.'ICEDHFBAJG'

which is the permutation 3;5;9 8 0 7 4 2 1 6. The instructions therefore are to tell the fourth and sixth people (that is numbers 3 and 5) to stay put; the person in the ninth position is to move to the tenth, the person in the first position to move to the ninth, and so on.

A permutation consisting only of 2-cycles is self-inverse. For n = 4, there are ten of these, one containing no 2-cycles, six containing a single 2-cycle corresponding to the 6 ways in which a pair of items can be chosen from four, and three containing two pairs of 2-cycles, viz. 3 2;1 0, 3 1;2 0 and 3 0;2 1. There are eight permutations with 3-cycles which form four mutually inverse pairs such as <3 0 2 and <3 2 0, and finally the number of 4-cycles is six, since a 4-cycle must have 3 as its first item and there are six ways in which the remaining three items can be permuted. Permutations can be classified as odd or even according to whether they are attainable as the result of an odd or an even number of successive two-item swaps from i.n. For example, 0 1 2 3->0 1 3 2->3 1 0 2, so 3 0 1 2 is the image of an even permutation. Analogously to the equilateral triangle, even permutations of i.4 correspond to the non-reflective symmetries of the tetrahedron, that is those which are physically realisable within three dimensional space.

The first six permutations in atomic ordering have 0 in their first position, the next six have 1 and so on. However apart from this, labelling by numerical order does not reflect logical structure within the set of all permutations of order 4. The table below classifies these permutations. 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. Subgroups of order 2 can be formed by combining 0 with any of the nine non-identity self-inverse permutations. The following form subgroups of orders 4, 8 and 12:

{0,7,16,23} {0,2,21,23} {0,1,6,7} {0,5,14,16}
{0,7,16,23,6,1,17,22} {0,7,16,23,14,9,5,18}

of which the last is the set of even permutations, called the alternating group A12.

And this is only the beginning of what they have at C. and A. – why don’t you pop round to the store and explore a bit for yourself?