16
$\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
  • 3
    $\begingroup$ Have you tried out PermutationList[FindPermutation[list]] or InversePermutation[Ordering[list]]? $\endgroup$ Mar 28, 2019 at 11:45
  • $\begingroup$ Thanks @J.M.. 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, 2019 at 13:44

1 Answer 1

16
$\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$
3
  • $\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, 2019 at 12:32
  • $\begingroup$ You're welcome. $\endgroup$ Mar 28, 2019 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, 2019 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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