Doc/Articles/Play131
At Play With J ... Table of Contents ... Previous Chapter ... Next Chapter
11. Riding a Unicycle
. By Eugene McDonnell. First published in Vector, 13, 1, (July 1996), 154-158.
This article deals with two topics dealing with permutations having a single cycle, which can be called unicycles. The first arises from a recent Internet inquiry, and the second resuscitates an obscure mathematician from two centuries ago to give him credit for having invented list processing.
We might ask how many unicycles there are for permutations of a given length. This number can be found by the use of Stirling numbers of the first kind, which came about precisely from a need to count the number of ways to arrange n objects into k cycles. In their APL95 paper, Representations of Recursion, Roger Hui and Ken Iverson give an efficient way to generate the table of values for these Stirling numbers for cycles:
S1v=: 1:`([S1r $:@<:) @. * " 0 S1r=: (0:,]) + <:@[ * ],0: S1v 4 0 6 11 6 1 S1v i.10 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 2 3 1 0 0 0 0 0 0 0 6 11 6 1 0 0 0 0 0 0 24 50 35 10 1 0 0 0 0 0 120 274 225 85 15 1 0 0 0 0 720 1764 1624 735 175 21 1 0 0 0 5040 13068 13132 6769 1960 322 28 1 0 0 40320 109584 118124 67284 22449 4536 546 36 1
As you can see, the number of ways that n objects can be arranged in a unicycle is !n-1.
I. The Bernecky Problem
Bob Bernecky, of Snake Island Research, in Toronto, sent a message on the Internet recently asking for help in deriving from the sequence of link fields in a linked list of records the permutation which would put the records into order. That is, suppose the records looked like this:
No. Name Link 0 Bee 6 1 Zee 0 2 Que 8 3 Gee 5 4 Pea 2 (A) 5 Jay 9 6 Dee 3 7 Vee 1 8 Tea 7 9 Key 4
The first record in the list is assumed to be in the leading position, but the locations of the other records is arbitrary. The 'Link' field in (A) gives the number of the successor record, and is 0 if it is the last record. In (A), the record following the first is number 6, and this is followed by number 3, which is followed by number 5, and so forth. It should be evident that the list of links is a permutation in (nonstandard) cycles form, in other words, a unicycle.
What was desired was to have the records arranged as follows:
No. Name Link 0 Bee 6 6 Dee 3 3 Gee 5 5 Jay 9 9 Key 4 (B) 4 Pea 2 2 Que 8 8 Tea 7 7 Vee 1 1 Zee 0
The desired permutation is given by the 'No.' field in display (B), that is, 0 6 3 5 9 4 2 8 7 1. My usual way of exploring such problems is to head in the general direction where I imagine a solution may be found, with no maps or guides or bearers, and just beat my way unaided through the jungle with a machete. To my satisfaction I found that I could obtain the solution by applying raze (;) to the cycles-direct (C.) of the link list, and rotating this result so that it begins with 0:
y=:6 0 8 5 2 9 3 1 7 4 (i.&0 |. ]) ; C. y 0 6 3 5 9 4 2 8 7 1
This is somewhat mysterious to me, since C. applied to an open list is supposed to convert from the direct form of a permutation to the cycles form, and here it looks as if the reverse is happening. (See the J Introduction and Dictionary for a description of the cycles and direct forms of a permutation.) Roger Hui provided me with the following explanation:
rot=: i.&0 |. ]
g0 =: 3 : '{&y^:(i.#y) 0'
f0 =: g0 { ]
fs =: {."1 @ ({/\) @ (i.@# , <:@# # ,:)
g1 =: rot@fs
f1 =: g1 { ]
g2 =: rot@;@C.
f2 =: g2 { ]
The g's (and therefore the f's) are equivalent on the vector x:
x=: 6 0 8 5 2 9 3 1 7 4 (g0 -: g1) x 1 (g0 -: g2) x 1
But they are not equivalent on arbitrary x:
g0 12?.12 0 10 3 4 6 1 2 5 7 9 8 0 g1 12?.12 0 10 3 4 6 1 2 5 7 9 8 0 g2 12?.12 0 11 10 3 4 6 1 2 5 7 9 8
In fact, the functions are equivalent exactly on those arguments that are a single cycle (1: = #@C.), and the explanation you seek lies in why g2=:rot@;@C. “works” on a single cycle.
The so-called “link list” representation of x:
0 1 2 3 4 5 6 7 8 9 x 6 0 8 5 2 9 3 1 7 4
specifies that 0 goes to 6, 6 to 3, 3 to 5, 5 to 9, etc., and that is what C. does in obtaining the cycle representation from the direct representation. If there is more than one cycle (if there is stuff left over from this process), C. then does it again on the remaining elements to get the next cycle.
Since the argument is a single cycle, the raze of what results simply removes the boxing, and the rotation converts from the J convention of starting a cycle by its maximal element to the alternative convention of starting a cycle from 0.
II. Crelle's Device
Histories of computing generally date the beginning of list-processing techniques to 1963 or so, with some possible smatterings of these techniques dating back to the days of Von Neumann, circa 1947. Imagine my surprise, then, to find that the date is off by over a hundred years.
The German engineer and mathematician August Leopold Crelle lived from 1780 to 1855. He made many minor contributions to mathematics, but is generally much better known as the founder and editor of the mathematical periodical Crelle's Journal. His foreshadowing of list processing is described in L. E. Dickson's monumental History of the Theory of Numbers (Vol. I, chap. VII, p. 185). First some discussion of primitive roots is necessary.
If we consider the powers of the positive numbers less than a given prime p, mod p, we note that some of these powers contain distinct elements, while others have repetitions. For example, when p=7 we get:
f=:] | [: ^/~ i.&.<: f 7 1 1 1 1 1 1 2 4 1 2 4 1 3 2 6 4 5 1 (C) 4 2 1 4 2 1 5 4 6 2 3 1 6 1 6 1 6 1
and we see that the numbers 1 2 4 6 give rise to rows with repetitions, but rows 3 and 5 contain distinct elements. This property of 3 and 5 is what characterizes them as primitive roots of 7. Dickson wrote (in 1918):
A. L. Crelle['s] ... device for finding the residues modulo p of the powers of a will be clear from the example p = 7, a = 3. Write under the natural numbers <7 the residues of the successive multiples of 3 formed by successive additions of 3; we get
1 2 3 4 5 6 3 6 2 5 1 4
Then the residues 3, 2, 6, of 3, 32, 33,... modulo 7 are found as follows: after 3 comes the number 2 below 3 in the table; after 2 comes the number 6 below 2 in the table; etc.
In other words, Crelle's device uses a linked list to convert from a list of multiples to a list of powers, mod some prime p. From the list
3 6 2 5 1 4
he produces
3 2 6 4 5 1
and this corresponds to the row beginning with 3 of table (C).
Crelle's list is clearly a single cycle, and thus a unicycle. His device works for each primitive root of a given prime. It is a way for converting from addition to multiplication, and is thus analogous to logarithms.
All hail Crelle, father of list processing!