12
$\begingroup$

Given a list list with unique elements, the task is to replace each element by its position in Sort[list]. For example,

list = {"A", "B", "D", "C", "Z", "W"};
Position[Sort[list], #][[1, 1]] & /@ list

{1, 2, 4, 3, 6, 5}

Much more efficient is to call Ordering twice:

Ordering[Ordering[list]]

{1, 2, 4, 3, 6, 5}

When applied on a permutation of Range[length] this operation does nothing:

list = {2, 10, 1, 4, 8, 6, 3, 9, 5, 7};
Ordering[Ordering[list]]

{2, 10, 1, 4, 8, 6, 3, 9, 5, 7}

Question: is there a more efficient way of doing this operation, making a single function call instead of calling Ordering twice?


benchmarks

Solutions are given from fastest to slowest:

L = RandomReal[{0, 1}, 10^7];

(* J.M.'s undocumented InversePermutation usage *)
R0 = InversePermutation[Ordering[L]]; // AbsoluteTiming // First
(* 2.39154 *)

(* Henrik Schumacher *)
R1[[Ordering[L]]] = R1 = Range[Length[L]]; //AbsoluteTiming//First
(* 2.42264 *)

(* original post *)
R2 = Ordering[Ordering[L]]; //AbsoluteTiming//First
(* 4.20186 *)

(* J.M. *)
R3 = PermutationList[InversePermutation[FindPermutation[L]]]; //AbsoluteTiming//First
(* 4.74717 *)

(* check *)
R0 == R1 == R2 == R3
(* True *)
$\endgroup$
  • 2
    $\begingroup$ Have you tried out PermutationList[FindPermutation[list]] or InversePermutation[Ordering[list]]? $\endgroup$ – J. M. will be back soon Mar 28 at 11:45
  • $\begingroup$ Thanks @J.M.isslightlypensive . I think that your use of InversePermutation on a permutation list instead of a permutation is undocumented. It's the fastest solution though. How do you know about all these undocumented tricks? $\endgroup$ – Roman Mar 29 at 13:44
12
$\begingroup$

No, Ordering[Ordering[list]] not optimal. And yes, there is a faster method:

list = RandomReal[{-1, 1}, 1000000];

First@RepeatedTiming[
  a[[Ordering[list]]] = a = Range[Length[list]];
  ]

First@RepeatedTiming[
  b = Ordering[Ordering[list]]
  ]

a == b

0.13

0.236

True

Edit

J.M.'s second suggestion is more concise and at least as fast if not slightly faster:

c = InversePermutation[Ordering[list]]; // RepeatedTiming // First

c == b

0.124

True

$\endgroup$
  • $\begingroup$ This solution cuts the effort down from two function calls to one function call plus one indexed substitution (very fast). 90% of what I was looking for, thanks! $\endgroup$ – Roman Mar 28 at 12:32
  • $\begingroup$ You're welcome. $\endgroup$ – Henrik Schumacher Mar 28 at 12:46
  • $\begingroup$ Thanks Henrik, I hadn't even checked J.M.'s second solution because I expected (according to the documentation) that InversePermutation spits out a permutation, not a permutation list. But that's not the case when you feed it a permutation list. $\endgroup$ – Roman Mar 29 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.