3
$\begingroup$

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}} *)
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Mr.Wizard
    May 2, 2014 at 11:55

7 Answers 7

7
$\begingroup$

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}}}
$\endgroup$
2
  • 1
    $\begingroup$ 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} &] $\endgroup$ May 2, 2014 at 11:35
  • 1
    $\begingroup$ 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] $\endgroup$
    – Mr.Wizard
    May 2, 2014 at 12:05
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ this is neat...these methods always seem much faster than sowing and reaping but I just like playing with Reap and Sow $\endgroup$
    – ubpdqn
    May 2, 2014 at 11:25
  • $\begingroup$ @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. $\endgroup$
    – Mr.Wizard
    May 2, 2014 at 11:34
4
$\begingroup$

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]
$\endgroup$
2
$\begingroup$

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).

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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}}}*)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.