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 1rfd 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
Contributed by RogerHui. 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.