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.