# Essays/Permutation Index

The monad` A. y `computes the index of permutation` y `in the sorted table of
all permutations of order` #y` .` `
The dyad` j A. i.n `computes the` j`-th permutation of order` n` .

A. 0 4 3 2 1 23 23 A. i.5 0 4 3 2 1 perm=: i.@! A. i. NB. table of all permutations perm 3 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0

Each number in` i.!n `has a unique representation
in the number system with` n-i.n `as bases, called
the *reduced representation*.
`A.` converts between a permutation index and
its reduced representation, and between the reduced
and the direct representations of a permutation,
to effect efficient computations.

base =: (-i.)@#@x: rfd =: +/@(<{.)\."1 NB. reduced from direct dfr =: /:@/:@,/"1 NB. direct from reduced adot1=: base #. rfd adot2=: dfr @ (base@] #: [) p=: 0 4 3 2 1 base p 5 4 3 2 1 rfd p 0 3 2 1 0 (base #. rfd) p 23 adot1 p 23 A. p 23 (base i.5) #: 23 0 3 2 1 0 dfr (base i.5) #: 23 0 4 3 2 1 23 adot2 i.5 0 4 3 2 1 23 A. i.5 0 4 3 2 1

`rfd `and` dfr `were originally written by E.E. McDonnell.

`adot1 `and` adot2 `(as does` A. `itself) use extended precision integers and
therefore work for permutations of any length.

(_1+!30x) adot2 i.30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 adot1 |. i.30 265252859812191058636308479999999 (_1+!30x) A. i.30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 A. |. i.30 265252859812191058636308479999999 !30x 265252859812191058636308480000000

**See also**

- Permutations
- Inverse Permutation
- Permutation Index
- Self-Upgrading Permutations
- Self-Downgrading Permutations
- Symmetric Array
- Symmetries of the Square
- Cayley's Theorem
- N Queens Problem

Contributed by Roger Hui. These ideas were previously discussed in section 3.3 of Ken Iverson's Turing lecture in 1979 and in comp.lang.apl on 1991-04-21.