# 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?

-

## 1 Answer

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)

-
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
@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
If I ever become a dairy farmer, I'm hiring you to milk my cows :P – R. M. Mar 16 '13 at 16:15