Fairly often I have a need to get the Ordering of an expression but with recognition of duplicates. For example:

Ordering[{0, 4, 1, 1, 2}]
{1, 3, 4, 5, 2}

but with duplicates such as 3, 4 marked, i.e.:

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

I have been using a decorate-and-sort followed by GatherBy and Part:

{0, 4, 1, 1, 2} //
  GatherBy[Sort[{#, Range@Length@#}\[Transpose]], First][[All, All, 2]] &
{{1}, {3, 4}, {5}, {2}}

Is there a better way?

up vote 22 down vote accepted

Yes, there is!

Szabolcs showed a use of GatherBy in an inverted fashion as a substitute for a conventional decorate-and-sort. It proved both syntactically and computationally efficient.

By using that method in place of the decorate-and-sort in this application we can use Ordering directly, and also eliminate Part which was needed to strip the decoration:

myOrdering[a_] := GatherBy[Ordering @ a, a[[#]] &]

{0, 4, 1, 1, 2} // myOrdering
{{1}, {3, 4}, {5}, {2}}

This is nearly twice as fast as my old method in the question, and much shorter.

I hope this function proves to be as useful to others as I know it will be to me.

Related posts: (21453), (29551)


Applying Carl Woll's revealing method from GatherByList to this problem we get:

myOrdering2[a_] :=
  Module[{f, o = Ordering @ a},
    f /: f /@ _ = a[[o]];
    GatherBy[o, f]
  ]

This can be significantly faster in cases with heavy duplication:

big = RandomInteger[100, 1*^6];

r1 = myOrdering[big];  // RepeatedTiming // First
r2 = myOrdering2[big]; // RepeatedTiming // First

r1 === r2
0.13

0.0930

True
  • So, looks like you've set the goal to get the most out of this method :-). +1, of course. – Leonid Shifrin Mar 16 '13 at 13:43
  • 1
    @Leonid As soon as I saw that it was fast I realized it was going to impact a number of applications. This is an operation for which I've been carting old code around without much thought. It's nice to finally get a clean and fast function for it. – Mr.Wizard Mar 16 '13 at 13:49
  • Yes, I agree. Just wondering why I did not discover that myself, since I had lots of similar problems too. I think that somehow I was sure the performance would be much worse, so I did not even bother trying. A big mistake, it turns out. – Leonid Shifrin Mar 16 '13 at 13:52
  • @Leonid Likewise, as I explained here. – Mr.Wizard Mar 16 '13 at 13:57
  • 2
    If I ever become a dairy farmer, I'm hiring you to milk my cows :P – rm -rf Mar 16 '13 at 16:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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