# Returning all positions for all different occurences of elements in a list

Is there way to construct oneliner as pure function(s), so that I enter mylist only on one place - on the end of line. And that function return the same result as last line bellow but paired with mylist. So the result should look like this:

{{1, {8}}, {2, {2, 4, 6}}, {4, {1}}, {5, {5}}, {7, {3, 7}}}

mylist = {4, 2, 7, 2, 5, 2, 7, 1};
alldiffelem = Sort@DeleteDuplicates@mylist
(* {1, 2, 4, 5, 7} *)
(Flatten@Position[mylist, #]) & /@ alldiffelem
(* {{8}, {2, 4, 6}, {1}, {5}, {3, 7}} *)

• Do you specifically want a "one-liner" constructed from anonymous functions? I can do that, but I think my present two-definition form is more clear. May 2, 2014 at 11:55

Here is an approach using Sow and Reap:

Last@Reap[MapThread[Sow, {Range[Length[mylist]], mylist}], _, List]


yielding

{{4, {1}}, {2, {2, 4, 6}}, {7, {3, 7}}, {5, {5}}, {1, {8}}}


if you wish to sort:

SortBy[Last@Reap[MapThread[Sow, {Range[Length[mylist]],mylist}], _, List], First]


yielding:

{{1, {8}}, {2, {2, 4, 6}}, {4, {1}}, {5, {5}}, {7, {3, 7}}}

• Nice. Reap and Sow seem more intuitive tools for this sort of task. Would be interested in timings on large lists. This is a bit more concise: Last@Reap[MapIndexed[Sow[First[#2], #1] &, mylist], _, {#1, #2} &] May 2, 2014 at 11:35
• An alternative to the SortBy method that appears to be twice as fast is: Last @ Reap[MapThread[Sow, {Range @ Length @ mylist, mylist}], Union @ mylist, List] May 2, 2014 at 12:05

This is almost a duplicate of Ordering function with recognition of duplicates. It is related to Efficiently finding the positions of a large list of targets in another, even larger list but since you apparently want all unique elements I believe it is closer to the first.

Using myOrdering from the first referenced question:

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

fn[a_List] := {Union @ a, myOrdering @ a}\[Transpose]

fn @ mylist

{{1, {8}}, {2, {2, 4, 6}}, {4, {1}}, {5, {5}}, {7, {3, 7}}}


### Version 10 update

The new-in-v10 GroupBy can combine the two lines of code in my original answer:

fn2[a_] := GroupBy[Ordering @ a, a[[#]] &]

<|1 -> {8}, 2 -> {2, 4, 6}, 4 -> {1}, 5 -> {5}, 7 -> {3, 7}|>


The result is an Association which has value in itself. However fn2 is not as fast as my original fn.

## Timings

Responding to Mike Honeychurch's implicit request for timings, here is my function (in its current version) versus both ubpdqn and his Sow/Reap method, performed in version 10.0.1.

mylist = RandomInteger[2*^5, 5*^5];

fn @ mylist  // Timing // First
fn2 @ mylist // Timing // First
Last@Reap[MapThread[Sow, {Range[Length[mylist]], mylist}], _, List] // Timing // First
Last@Reap[MapIndexed[Sow[First[#2], #1] &, mylist], _, List]        // Timing // First

0.265202

0.702005

3.619223

4.118426


Note that both Sow/Reap methods are the un-sorted variation; adding a sort would incur an additional overhead.

• this is neat...these methods always seem much faster than sowing and reaping but I just like playing with Reap and Sow May 2, 2014 at 11:25
• @ubpdqn I like Sow and Reap too. +1 on your answer. By the way I just fixed my code which was broken due to confusing myself re: sorting. May 2, 2014 at 11:34

Competitive with fastest so far in general, and often considerably faster (e.g., when duplication of elements is higher, as in RandomInteger[5000, 1000000] about 3 to 4X faster):

Module[{o, d = DeleteDuplicates@mylist, r = Range@Length@mylist},
o = Ordering@d;
Transpose[{d, GatherBy[r, mylist[[#]] &]}][[o]]]


As a pure function:

With[{d = DeleteDuplicates@#, l = #, r = Range@Length@#},
Transpose[{d, GatherBy[r, l[[#]] &]}][[Ordering@d]]] &[mylist]


Using SparseArray and changing the setting of TreatRepeatedEntries suboption (of SparseArrayOptions in SystemOptions:

SystemSetSystemOptions["SparseArrayOptions"->{"TreatRepeatedEntries"->(ToString[{##}]&)}];
xx = SparseArray[mylist -> Range[Length[mylist]]]["NonzeroValues"] // ToExpression;
SystemSetSystemOptions["SparseArrayOptions" -> {"TreatRepeatedEntries" -> First}];
yy = SparseArray[mylist -> mylist]["NonzeroValues"];
Transpose[{yy, xx}]
(* {{4, 1}, {2, {2, 4, 6}}, {7, {3, 7}}, {5, 5}, {1, 8}}  *)


(See O. Rubenko's answer Fast 2D binning for this undocumented suboption. See also Optimizing 2D binning code)

Note: this approach works in the current form for "target lists of positive integers of limited range" (e.g., on my machine, it works for a list of length 50,000, but 100 000 does not) . (thanks: @rasher).

• I think it is worth to add a link to the post where undocumented "TreatRepeatedEntries" suboption is explained. May 3, 2014 at 6:37
– kglr
May 3, 2014 at 7:46
• You should note this is only usable in this form with target lists of positive integers of limited range.
– ciao
May 3, 2014 at 7:54
• @rasher, thanks; just updated with the suggested note.
– kglr
May 3, 2014 at 8:49

mylist only on one place - on the end of line

Sort@(Function[{x, y},
Thread[List[y, Flatten@Position[x, #] & /@ y]]] @@ {#,DeleteDuplicates@#}) &@mylist


{{1, {8}}, {2, {2, 4, 6}}, {4, {1}}, {5, {5}}, {7, {3, 7}}}

Via PositionIndex

mylist = {4, 2, 7, 2, 5, 2, 7, 1};

foo = KeyValueMap[List] @ KeySort @ PositionIndex @ #&;

foo @ mylist


{{1, {8}}, {2, {2, 4, 6}}, {4, {1}}, {5, {5}}, {7, {3, 7}}}

Using MapIndexed and the third argument of GroupBy:

lst = {4, 2, 7, 2, 5, 2, 7, 1};

Values@GroupBy[Sort@MapIndexed[List, lst], First,
{#[[1, 1]], #[[2, All, 1]]} &@Transpose@# &]

(*{{1, {8}}, {2, {2, 4, 6}}, {4, {1}}, {5, {5}}, {7, {3, 7}}}*)