Ordering function with recognition of duplicates

Question

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?

Answer 1

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

Answer 2

Using Association - related functions (which were not available at the time the question was posted):

list = {0, 4, 1, 1, 2};

Values @ KeySort @ PositionIndex @ list

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