# Ordering function with recognition of duplicates

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?

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. Mar 16 '13 at 13:43
• @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. 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. Mar 16 '13 at 13:52
• @Leonid Likewise, as I explained here. Mar 16 '13 at 13:57
• If I ever become a dairy farmer, I'm hiring you to milk my cows :P
– rm -rf
Mar 16 '13 at 16:15