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

Question

Is there a way to construct one-liner as pure function(s), so that I enter mylist only on one place - on the end of the line. And that function return the same result as last line below 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}} *)

Answer 1

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}}}

Answer 2

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.

Answer 3

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]

Answer 4

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

System`SetSystemOptions["SparseArrayOptions"->{"TreatRepeatedEntries"->(ToString[{##}]&)}];
xx = SparseArray[mylist -> Range[Length[mylist]]]["NonzeroValues"] // ToExpression;
System`SetSystemOptions["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).

Answer 5

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}}}

Answer 6

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}}}

Answer 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}}}*)

Answer 8

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

f = Function[p, {p, Flatten @ Position[list, p]}, Listable];

f[Union @ list]

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