20. Inverse Permutation

⍋p

The inverse of a permutation p is a permutation q such that p[q] ≡ ⍳≢p . It can be computed in several ways:

⍋p
p⍳⍳≢p
q⊣q[p]←⍳≢q←p

The first two can be found in [3b]; the third is part of the APL folklore by the 1970s. It used to be that the third expression is preferred even though it is longer and more obscure, because it runs in linear time and was much faster. The imbalance has been addressed in modern APL implementations on small as well as large arguments. In Dyalog APL version 15.0 [74]:

   p←?⍨131
   cmpx '⍋p' 'p⍳⍳≢p' 'q⊣q[p]←⍳≢q←p'
⍋p           → 3.61E¯7 |    0% ⎕⎕⎕⎕
p⍳⍳≢p        → 8.29E¯7 | +129% ⎕⎕⎕⎕⎕⎕⎕⎕⎕
q⊣q[p]←⍳≢q←p → 2.75E¯6 | +661% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   p←?⍨10000019
   cmpx '⍋p' 'p⍳⍳≢p' 'q⊣q[p]←⍳≢q←p'
⍋p           → 1.46E¯1 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
p⍳⍳≢p        → 1.44E¯1 | -2% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
q⊣q[p]←⍳≢q←p → 1.39E¯1 | -5% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

There are no good reasons to avoid ⍋p any more.