# Gather list elements by index

The following list has some elements that are labeled. For example {1, 2} -> 1, {-1, 3} -> 3, etc:

list = {{1, 2}, {-1, 3}, {5, 6}, {-3, 4}, {7, 8}, {-9, 1}, {0, 1}};
labels = {1, 3, 2, 1, 2, 1, 3};


What is a good way to gather list's elements clustered according to their labels?

clusters = {{{1 ,2}, {-3, 4}, {-9, 1}}, {{5, 6}, {7, 8}}, {{-1, 3}, {0, 1}}}

-
I think there was a question like this in the past but I can't recall it. Extract[list, Position[labels, #]] & /@ Union@labels – Kuba Jul 15 '13 at 13:10
@Kuba. Please write up your solution as an answer so we can get this question off the unanswered list. – m_goldberg Jul 15 '13 at 13:21
After 5 days i will run a benchmark for all answers (with reasonable data) and post here the results. – tchronis Jul 15 '13 at 13:58
@tchronis More than five days have passed, and you've got two new answers. I chose to add timings to my own. I'll be interested to see your own timings when you get around to it. – Mr.Wizard Jul 31 '13 at 10:47
Thanks for the Accept. :-) – Mr.Wizard Nov 29 '13 at 12:34

I believe the best way is to use an Ordering function with recognition of duplicates.
Please see that (self) Q&A for an explanation.

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

list[[#]] & /@ myOrdering[labels]

{{{1, 2}, {-3, 4}, {-9, 1}}, {{5, 6}, {7, 8}}, {{-1, 3}, {0, 1}}}


## Timings

Here are timings of each of the methods posted so far that produce the requested output.

list = RandomInteger[999, {3000, 2}];
labels = RandomInteger[999, 3000];

timeAvg =
Function[func,
Do[If[# > 0.3, Return[#/5^i]] & @@ Timing@Do[func, {5^i}], {i, 0, 15}],
HoldFirst];

Extract[list, Position[labels, #]] & /@ Union@labels // timeAvg

Pick[list, labels, #] & /@ Union@labels // timeAvg

GatherBy[
Sort[Transpose@{labels, list}, OrderedQ[{#1[[1]], #2[[1]]}] &],
First
][[All, All, 2]] // timeAvg

Reap[MapThread[Sow, {list, labels}], Union @ labels][[2, All, 1]] // timeAvg

list[[#]] & /@ myOrdering[labels] // timeAvg


0.0966

0.2184

0.02992

0.002872

0.0013728

(Note: these timings were performed in version 7; Pick was improved in version 8, and may yield better timings for others. With labels = RandomInteger[10, 3000] Kuba reports 0.000625001 for Pick and 0.00057500 for myOrdering. Nevertheless the multi-pass nature of the Pick solution will slow down with an increasing number of unique labels.)

-
Performance depends of labels variety. Try labels = RandomInteger[10, 3000], Pick should show it's strength :) – Kuba Jul 31 '13 at 10:39
@Kuba It's still nearly an order of magnitude slower than myOrdering on my system. I know Pick was improved on Packed Arrays in version 8 (I use v7). What timings do you get? Nevertheless I think the multiple-pass Pick/Position method has a higher complexity by nature. – Mr.Wizard Jul 31 '13 at 10:44
0.000625001 for Pick and 0.00057500 for myOrdering :) – Kuba Jul 31 '13 at 10:51
@Kuba I added a note to my answer; I hope you approve. – Mr.Wizard Jul 31 '13 at 10:58
I fully agree :) I was aware of not efficient nature of this approach, I should have described it but I forgot :) – Kuba Jul 31 '13 at 11:02

I'm always afraid in case of that there was a duplicate in the past. But I do not remember.

You can try this:

Extract[list, Position[labels, #]] & /@ Union@labels


{{{1 ,2}, {-3, 4}, {-9, 1}}, {{5, 6}, {7, 8}}, {{-1, 3}, {0, 1}}}

and this:

Pick[list, labels, #] & /@ Union@labels


{{{1, 2}, {-3, 4}, {-9, 1}}, {{5, 6}, {7, 8}}, {{-1, 3}, {0, 1}}}

GatherBy variation

GatherBy[Sort@Thread[Rule[labels, list]], First][[ ;; , ;; , 2]]


{{{-9, 1}, {-3, 4}, {1, 2}}, {{5, 6}, {7, 8}}, {{-1, 3}, {0, 1}}}

-

My GatherBy variation:

GatherBy[Transpose@{labels, list}, First][[All, All, 2]]


{{{1, 2}, {-3, 4}, {-9, 1}}, {{-1, 3}, {0, 1}}, {{5, 6}, {7, 8}}}

A possible drawback is that the result is not sorted by label. This is easy to change by doing

GatherBy[Sort@Transpose@{labels, list}, First][[All, All, 2]]


{{{-9, 1}, {-3, 4}, {1, 2}}, {{5, 6}, {7, 8}}, {{-1, 3}, {0, 1}}}

which sorts by label but destroys the initial intra-label ordering or by

GatherBy[Sort[Transpose@{labels, list}, OrderedQ[{#1[[1]], #2[[1]]}] &], First][[All, All, 2]]


{{{1, 2}, {-3, 4}, {-9, 1}}, {{5, 6}, {7, 8}}, {{-1, 3}, {0, 1}}}

which keeps the initial order.

-
Thank you @sebhofer. Yes the non sorted drawback matters in my case. – tchronis Jul 15 '13 at 13:39
@tchronis I realised this is easy to change, see my edit. – sebhofer Jul 15 '13 at 13:44
Another idea for the sorting might be: Sort[GatherBy[Transpose[{labels, list}], First], First@#1[[1]] < First@#2[[1]] &][[All, All, 2]] (possibly slower than your ideas, but at least it's rather short :) ) – Pinguin Dirk Jul 15 '13 at 16:55
@PinguinDirk Sure that also works, I would contest it's shorter though. You can do Sort[GatherBy[Transpose[{labels, list}], First], #1[[1, 1]] < #2[[1, 1]] &][[All, All, 2]] then it is shorter, but only by 7 keystrokes :) – sebhofer Jul 15 '13 at 17:07
ok :) it's not code golfing, and I'd have chosen the same approach! +1 – Pinguin Dirk Jul 15 '13 at 17:10

This also works:

Reap[MapThread[Sow, {list, labels}]][[2]]


or an alternatively ordering by tags:

Reap[MapThread[Sow, {list, labels}], Union @ labels][[2, All, 1]]

-
I really like Sow and Reap. (+1) I hope you don't mind, but I'm taking the liberty to streamline your code; you can revert the edit if you disapprove. – Mr.Wizard Jul 31 '13 at 10:11
Value your comment and edit. I always learn something. – ubpdqn Jul 31 '13 at 10:36
Thanks: Reap/Sow seemed a useful approach. I just failed to understand it well enough, My ignorance, I hope, is now further reduced. – ubpdqn Aug 1 '13 at 0:59
What you had was perfectly valid. It is simply that the default values work in this case so we aren't required to specify them. Regarding using Sow[#, #2]& rather than simply Sow, I've seen many people do that so you're in good company. :-) – Mr.Wizard Aug 1 '13 at 1:04