21. Permutation Index

The permutation index of a permutation p is its index in the sorted matrix of all permutations. That is, for perm from Chapter 19,

   p←2 0 3 4 1

   (perm ≢p)⍳p
51

   51⌷perm 5
2 0 3 4 1

It is desired to compute the permutation index without materializing the matrix of all permutations.

Each number in ⍳!n has a unique representation in the coordinate system with n-⍳n as bases, called the reduced representation; by back formation, the permutations are called the direct representation. Since there are !n permutations, there exists a 1-to-1 relationship between these representations. The algorithms rfd and dfr , discovered by Eugene McDonnell in 1968 [75], convert between them.

   rfd  ← {⍵+.>¨(⍳≢⍵)↓¨⊂⍵}     ⍝ reduced     from direct
   dfr  ← {⊃(⍋∘⍋,)/⍵}          ⍝ direct      from reduced

   base ← {n-⍳n←≢⍵}
   ifp  ← base ⊥ rfd           ⍝ index       from permutation
   pfi  ← {dfr(base⍳⍺)⊤⍵}      ⍝ permutation from index

   p←1 3 0 7 6 5 4 9 8 2

   rfd p
1 2 0 4 3 2 1 2 1 0
   dfr rfd p
1 3 0 7 6 5 4 9 8 2

   ifp p
446819
   10 pfi ifp p
1 3 0 7 6 5 4 9 8 2

pfi requires a left argument because from the permutation index alone it is not possible to determine the order (length) of the permutation.

   odometer 3-⍳3    ⍝ odometer from Chapter 28
0 0 0
0 1 0
1 0 0
1 1 0
2 0 0
2 1 0
   dfr⍤1 odometer 3-⍳3
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
   (perm 3) ≡ dfr⍤1 odometer 3-⍳3
1

These functions do not work for permutations of order greater than 18 on IEEE 64-bit floating numbers because such numbers run out of precision at 2*53 (18.1169=!⍣¯1⊢2*53). However, the algorithms are valid on extended precision numbers. In J:

   ] p=: i._37
36 35 34 33 32 31 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
   ifp p
13763753091226345046315979581580902399999999
   !37x
13763753091226345046315979581580902400000000

   37 pfi ifp p
36 35 34 33 32 31 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

Anecdote

Sometime in the 1970s, Eugene McDonnell visited some members of the I.P. Sharp language development group (“the Zoo”) on the Toronto Islands, and told them about the rfd and dfr functions. When the Islanders eventually, finally, figured out how these functions worked, they burst out laughing.

Appeared in J [76, 77].