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.