Answers to J Problems from Vector 11.3

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

Eugene McDonnell raises a number of issues in "At Work and Play with J" (Vol.11 No.3). The first is implicit in the casual remark that to exercise the verbs in the later sections you "may wish to get your system upgraded to J8". This fails to recognise that J8 and beyond are commercial versions and thus outwith the "shareware barrier". I am personally happy that version 7 has stabilised as an excellent piece of software with such immense possibilities for exploration at work and play that commercial style add-ons seem almost an irrelevance. Perhaps, however, Eugene might consider marking sections of his material with, say, *** to indicate "For Rich Readers Only". Poor readers such as myself can then get on with more interesting matters such as the problems which Eugene set. He asks for solutions by e-mail; being a very poor reader I have chosen to reply by v-mail (v = Vector) which has the compensation that my reply may reach a slightly wider audience.

Problem 1 asks for permutations of order n which, when repeatedly applied, generate, in the sense described below, all 2!n combinations from i.n without any repetitions. First, the word "permutation" has always created difficulties because it is used to denote both a permutation vector, that is an arrangement of the items of i.n, and also an operation, of which J commendably makes it easy to make the distinction by defining a verb p=.&{. In what follows I shall use the word "permutation" in the sense of the operation and "permutation vector" to mean data. The permutation which is represented by a permutation vector has to be understood by constructing its cycle representation, conveniently obtained by C., each item of which is a vector such as 4 0 2 1, which is to interpreted as a sub-operation which moves item 0 to position 4, item 2 to position 0, item 1 to position 2, and item 4 to position 1. Eugene therefore seeks permutation vectors which when cycled through the i.n-1 powers of the permutation which they represent fulfil the pairs criterion — I shall call such vectors qualifying vectors.

If n=6, one qualifying vector is 5 2 0 3 1 4 because when as a permutation it is applied to itself to the powers 0,1,2,3,4 it generates the permutation vectors

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

which read in sequence by rows as unordered pairs of items produce each of the fifteen pairs (0,1) (0,2), … (4,5) once and once only.

For n=6, the (n-1)-cycle requirement can be met by fixing just one of the items in i.6 (which happens to be 3 in the permutation vector above) and making a derangement of the remaining (n-1). (A derangement is a permutation vector in which no item occupies its original place). The fixed item can be selected in n ways. Suppose that in the general case it is chosen to be the last item n-1, so that the problem becomes one of selecting a derangement of i.n-1. If (n-1) is prime, this is the only way in which Eugene’s cycling property can be achieved. Not all derangements, however, satisfy the pairs property, for example the permutation 1 2 3 4 0 5 produces only six of the fifteen possible pairs.

The pairs property is derived by slicing the matrix of successive permutations into pairs of columns. This is difficult to relate in a mathematical way to other properties of permutations, but fortunately the J verb A. allows permutation vectors to be assigned numbers uniquely, so that qualifying permutation vectors can be found (all of them in the case that (n-1) is prime) by the following procedure:

Use A. to progress through selected permutation vectors of n-1, selecting only those which satisfy the derangement property. For these derangements, generate the full (n-1) cycle, append (n-1), and count the number of distinct rows in the 2!n-1 by 2 matrix of pairs. If this is 2!n-1 then a single qualifying vector has been found.

The permutation vectors obtained by cycling, although they represent different permutations, should not be retained since they will eventually reappear as the full set of derangements is searched.

The J code to achieve this is relatively mundane, but it is worth quoting on account of its brevity (I have chosen to refrain from tacit programming snobbery!):

cycle=.'(y.&{)^:(i.<:#y.)i. # y.' : ''
NB. returns y. raised by the permutation y. to the powers 0..n-1
b=.'(2!#y.)=#~./:~"1((2!#y.),2)$,cycle y.' :''
NB. returns 1 if all possible pairs arise in the matrix of cycles
d=.'-.+./y.=i.#y.' : ''
NB. returns 1 if perm vector is a derangement, otherwise 0

s1=.'i=.!y. [ $.=.x.#1 [ r=.(0,y.)$0'
s2=.'r=.r,((d*.(b@,&y.)v),y.)$v=.(i=.i-1) A. i.y.'
NB. s1 and s2 are the two lines of a dyadic verb f which searches
NB. the last x. permutation vectors of order y. and retains
NB. only those derangements which lead to qualifying vectors when
NB. y. is appended.
f=.'' : (s1;s2)

thus (6 f 3),.3 gives two of Eugene’s set of eight qualifying vectors of length 4. The remaining six arise by keeping 0, 1, and 2 in succession in their home locations. The reason for looping downwards from !y. is that A. orders permutation vectors in lexical order, which means that the first !i.y.-1 have their leading numbers in their "home" positions, and so cannot be derangements.

Turning to Eugene’s problem 2, that is how many qualifying vectors are there of order n, unfortunately the number of derangements of n increases rapidly with n, the first few values being

n : 2 3 4 5 6 7 8 9 10
no. of der’s : 1 2 9 44 265 1854 14833 133496 1334961

An "elegant" approach might be to obtain all derangements of order y. by

  der=.'(d"1 t)#t=.(i.!y.)A.i.y.' : ''

and then select those satisfying the pairs criterion by

  ans=.'((b"1 t,.y.)#t=.der y.),.y.' : ''

Unfortunately for those of us who, like myself, work and play at or below the poverty line, this produces "ws full" for n=8 — hence the looping approach given above. Even this rapidly runs up against a wall of patience and/or "ws full" limitations as n increases.

For n=4, there are two fundamental permutation vectors corresponding to each of the two derangements of order 3. This is then is multiplied by four to account for the fact that each of the items of i.4 can be placed in its "home" position. Division by !4 shows that one-third of all possible permutation vectors qualify.

In the case of n=6, there are 44 derangements of order 5 of which eight satisfy the pairs condition. Multiply by n=6 to give 48 possible permutation vectors, a qualifying rate of 48/720 = one in fifteen.

For n=8 and above I have resorted to sampling. By looping through the first 500 derangements of order 7 using 500 f 7 I obtained 24 suitable ones leading to 192 qualifying vectors. Given that the search covered about one-eighth of the possible derangements, this figure scales up to an estimated qualifying rate of about one in 25.

For n=10, and again looping 500 times, I obtained 6 derangements and hence 600 qualifying vectors, suggesting a rate of about one in 100. For n=12, 500 times round the loop produced only one suitable derangement and thus 12 permutation vectors suggesting a rate of about one in 6000. As n increases there are more and more qualifying vectors but they become progressively less dense.

If, for a largish n, the objective is to obtain just one qualifying vector — any one — then an appropriate policy might be to repeatedly select a random left argument to A. from the range i.!n until the first qualifying vector is generated.