Doc/Articles/Play121
At Play With J ... Table of Contents ... Previous Chapter ... Next Chapter
7. Representing a Permutation
. By Eugene McDonnell. First published in Vector, 12, 1, (July 1995), 125-128.
This column explores some ways of changing among different ways of representing a permutation.
Representations of a permutation:
standard reduced atomic
0 1 2 0 0 0 0
0 2 1 0 1 0 1
1 0 2 1 0 0 2
1 2 0 1 1 0 3
2 0 1 2 0 0 4
2 1 0 2 1 0 5
The tables above give three different forms of length-3 permutations. It is useful to be able to go between the standard and the atomic forms, and this conversion is facilitated by the reduced form. We develop the following verbs:
ra reduced from atomic ar atomic from reduced sr standard from reduced rs reduced from standard
with these we can convert from each of the forms to any other.
A factorial digits number base is used to convert between the atomic and reduced forms. The verb fdb gives the factorial digits base for permutations of the order of its argument.
fdb=: >:@i.@-
For example,
fdb 3 3 2 1
With this base we can convert an atomic to a reduced form and vice-versa:
(fdb 3)#: 4 2 0 0 (fdb 3)#. 2 0 0 4
So the two verbs ra and ar are easily defined:
ra=: ([: fdb [) #: ] ar=: ([: fdb #) #. ]
For example:
3 ra 4 2 0 0 ar 2 0 0 4
To convert from a reduced to a standard form is somewhat more difficult. The trick is to begin at the right and add 1 to each atom which is equal to or greater than the atom at the left. This ensures that all atoms are kept distinct, and that at each step we have a permutation. For example, suppose we take the length 9 reduced form of the atomic form 288918:
]r=: (fdb 9) #: 288918 7 1 2 1 3 1 0 0 0
and then work from the right to develop the standard form:
0
0 1
0 1 2
1 0 2 3
3 1 0 2 4
1 4 2 0 3 5
2 1 5 3 0 4 6
1 3 2 6 4 0 5 7
7 1 3 2 6 4 0 5 8
and the last result is the desired standard form. We could define a function that follows this procedure, but we can do better than this, employing an identity I discovered in 1968. For integer k and permutation p ,
k , p + p >: k ←→ /: /: k , p
and arrive finally at the desired verb:
sr=: /: @ /: @ , / ] s=: sr r 7 1 3 2 6 4 0 5 8
The last verb we need, to translate from standard to reduced form, is arrived at by noting that, if r is the reduced form of a standard form s , then i{r is obtained from i{s by taking a count of how many atoms to the right of i{s are less than i{s . For example:
7 1 3 2 6 4 0 5 8
7 > x x x x x x x x = 7
1 > x = 1
3 > x x = 2
2 > x = 1
6 > x x x = 3
4 > x = 1
0 > = 0
5 > = 0
8 > = 0
J provides two related adverbs, prefix and suffix. The first, prefix, is applied to longer and longer prefixes, whereas suffix is applied to shorter and shorter suffixes. Thus the rs verb we need can be defined as:
rs=: ([: +/ }. < {.)\.
rs s
7 1 2 1 3 1 0 0 0
With these four verbs, it is possible to obtain any of the three forms from any other. We don't need a verb to go directly from standard to atomic or vice-versa. However, J provides this as a primitive verb, denoted by A. and called Atomic Index for its monad and Atomic Permute for its dyad. For example,
A. s 288918 288918 A. i. 9 7 1 3 2 6 4 0 5 8
So with A. a primitive, the four verbs we labored over above are more interesting for pedagogical than for practical reasons.
Atomic permute doesn't care what its right argument is; it will permute any object of sufficient length:
288918 A. 'netrilacy' certainly
A useful verb to generate a table of all permutations of a given length is easy to write:
apn=: i.@! A. i. apn 3 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0
You would need a computer with a rather large amount of main store to generate apn 12 -- about 46e9 bytes (8 bytes per element, 12 elements per row, 479,001,600 rows). Of course, the computer would also have to be able to address that large a store, too. Judging from the current state of affairs, it may well be almost the year 2000 before we routinely have these capabilities on our desktops.