# 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.