13
$\begingroup$

Say, we have a list:

m1 = {2, 2, 7, 0, 7, 7, 2, 2, 2}

It can be split easily:

Split @ m1
(* {{2, 2}, {7}, {0}, {7, 7}, {2, 2, 2}}  *)

Wanted: a method to get the following list:

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

It should be as simple as possible and fast for long lists.

Improve this question
$\endgroup$
1

11 Answers 11

Reset to default
14
$\begingroup$

You can use

SplitBy[Range@Length@m1, m1[[#]] &]
Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ Immortal solution $\endgroup$
    – garej
    Commented Jan 23, 2016 at 10:03
  • 1
    $\begingroup$ so clean and nice +1 :-) $\endgroup$
    – ubpdqn
    Commented Jan 23, 2016 at 10:09
  • 1
    $\begingroup$ +1 Looks useful. Is there some way to illustrate how this works? $\endgroup$
    – Chris Degnen
    Commented Jan 23, 2016 at 11:24
  • 1
    $\begingroup$ As discussed here, Split and SplitBy are very slow for long list. I've tried it with m1 = Flatten[Table[#, # + 1] & /@ RandomInteger[{1, 100}, 10^5]]; and it is order of magnitude slower that counterparts. $\endgroup$
    – garej
    Commented Jan 23, 2016 at 12:11
  • 1
    $\begingroup$ How it works: see output list = {}; SplitBy[ Range@Length@m1, (AppendTo[list, #]; m1[[#]]) &]; list plus docs SplitBy[list,f] splits list into sublists consisting of runs of successive elements that give the same value when f is applied. $\endgroup$
    – Chris Degnen
    Commented Jan 23, 2016 at 14:33
9
$\begingroup$

There is a complicated trade-off between the speed and compact form in this case, so I have decided to post the version with Range, which I consider simple enough (comprehensible for new users) and second fast among the conterparts (at least, on my machine).

It is heavily based on @Mr.Wizard solution farsightedly provided by ChrisDegnen, so I do not claim originality:

dynS[p_] := Range @@@ Thread[{Accumulate@p - p + 1, Accumulate@p}]

Method

And after looking at @Mr.Wizard SparseArray solution I finally realize that we may use Listable attribute of Range to get even more compact version (this time I would prefer to keep pure function notation #). So this is favorite method for me (not mine :)!

dynSP[p_] := Range[# - p + 1, #]& @ Accumulate @ p

Timing benchmarking

I use the long list for benchmarking:

m1 = Flatten[Table[#, # + 1] & /@ RandomInteger[{1, 200}, 10^5]];
Length[m1]
(* 10156647 *)

And packed version later (second timing output in each method).

m1 = Developer`ToPackedArray[m1];

Range[Prepend[# + 1, 1], Append[#, Length @ m1]] & 
@ SparseArray[Differences @ m1]["AdjacencyLists"] // Length // RepeatedTiming
(* {0.403, 99530} *)
(* {0.274, 99489} *)

dynSP[Length /@ Split @ m1] // Length // RepeatedTiming
(* {0.476, 99439} *)
(* {0.626, 99439} *)

dynS[Length /@ Split @ m1] // Length // RepeatedTiming
(* {0.506, 99495} *)
(* {0.715, 99489} *)

Internal`PartitionRagged[Range[Length@m1], Length /@ Split@m1] // Length // RepeatedTiming
(* {0.589, 99495} *)
(* {0.78, 99489}  *)

dynP[Range@Length@m1, Length /@ Split @ m1] // Length // RepeatedTiming
(* {0.613, 99495} *)
(* {0.83, 99489}  *)

Module[{i = 1}, Replace[Split@m1, _ :> i++, {-1}]] // Length // RepeatedTiming
(* {3.845, 99439} *)
(* {4.1, 99439}   *)

Module[{i = 0}, Map[++i &, Split[m1], {-1}]] // Length // RepeatedTiming
(* {6.57, 99495} *)
(* {6.85, 99489} *)

SplitBy[Range @ Length @ m1, m1[[#]] &] // Length // RepeatedTiming
(* {24.6, 99495} *)
(* {25., 99489}  *)

Note: fastest function with SparseArray has been added a bit later so its result in terms of length is slightly different. The same is for the Module with Split version and my favorite DynSP.

Improve this answer
$\endgroup$
0
8
$\begingroup$

Perhaps:

s = Split@m1;
Internal`PartitionRagged[Range[Length@m1], Length /@ s]
Improve this answer
$\endgroup$
1
  • $\begingroup$ oh, nice, I've missed such possibility, thank you. Related $\endgroup$
    – garej
    Commented Jan 23, 2016 at 10:01
7
$\begingroup$

Internal`CopyListStructure is quite fast:

Internal`CopyListStructure[Split @ #, Range @ Length @ #] & @ m1

 {{1, 2}, {3}, {4}, {5, 6}, {7, 8, 9}}
Improve this answer
$\endgroup$
1
  • $\begingroup$ thank you, I did not know about this structure. Upvoted a couple of similar questions. $\endgroup$
    – garej
    Commented Jan 2, 2021 at 13:25
6
$\begingroup$

Too late for the party so here's something old style:

Module[{i = 0}, Map[++i &, Split[m1], {-1}]]

or

SplitBy[MapIndexed[Flatten@*List, m1], First][[;; , ;; , 2]]
Improve this answer
$\endgroup$
1
  • $\begingroup$ it is never too late to make a good contribution. I like the old style... $\endgroup$
    – garej
    Commented Jan 23, 2016 at 19:52
5
$\begingroup$

Using Mr.Wizard's ragged partition function here

dynP[l_, p_] := MapThread[l[[# ;; #2]] &,
  {{0}~Join~Most@# + 1, #} &@Accumulate@p]

m1 = {2, 2, 7, 0, 7, 7, 2, 2, 2};
m2 = Split@m1;

dynP[Range@Length@m1, Length /@ m2]

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ ,thank you, ironically I saw this solution a year ago but was incapable to grasp it :)) $\endgroup$
    – garej
    Commented Jan 23, 2016 at 10:21
5
$\begingroup$ 
m1 = {2, 2, 7, 0, 7, 7, 2, 2, 2};
Module[{i = 1}, Replace[Split@m1, _ :> i++, {-1}]]
(* {{1, 2}, {3}, {4}, {5, 6}, {7, 8, 9}} *)
Improve this answer
$\endgroup$
3
  • $\begingroup$ @Mr.Wizard, I remember warnings concerning Block, so never use(d) it. $\endgroup$
    – garej
    Commented Jan 24, 2016 at 19:06
  • $\begingroup$ @Mr.Wizard. That's interesting. I should go read the use cases for different scoping constructs post again. $\endgroup$
    – march
    Commented Jan 24, 2016 at 19:06
  • $\begingroup$ march, using Block incorrectly seems to get a lot of people; as stated I did it myself many times before more experienced users (Szabolcz or Leonid probably) pointed out my mistake. Even Wolfram developers do it! Using his code on numbering[{{a, b}, {m, n}, {x, y}}] for example note that n has been incorrectly replaced by 0 in the output. $\endgroup$
    – Mr.Wizard
    Commented Jan 24, 2016 at 19:12
4
$\begingroup$

Adapted from my answer to a related question:

runs[a_List] := 
 Range[Prepend[# + 1, 1], Append[#, Length@a]] &@
  SparseArray[Differences@a]["AdjacencyLists"]

Now:

runs @ {2, 2, 7, 0, 7, 7, 2, 2, 2}

{{1, 2}, {3}, {4}, {5, 6}, {7, 8, 9}}
Improve this answer
$\endgroup$
3
  • $\begingroup$ Oh, SparseArray!!! I was about to ask how to apply it here :))) $\endgroup$
    – garej
    Commented Jan 24, 2016 at 19:32
  • $\begingroup$ @garej Glad I could be of help. :-) Please add this to your benchmark. $\endgroup$
    – Mr.Wizard
    Commented Jan 24, 2016 at 19:34
  • $\begingroup$ @garej I see that a new syntax has been added for Table, after version 10.1.0 (which I use). Anyway (at least in 10.1) your m1 is not packed; would you please try your benchmark also with m1 = Developer`ToPackedArray[m1]; ? $\endgroup$
    – Mr.Wizard
    Commented Jan 24, 2016 at 19:42
3
$\begingroup$

I'll add another option, but be warned: It's rather slow.

FoldPairList[TakeDrop, Range@Length@m1, Length /@ (Split @ m1)]
Improve this answer
$\endgroup$
1
  • $\begingroup$ yes, it hangs my machine with m1 = Flatten[Table[#, # + 1] & /@ RandomInteger[{1, 100}, 10^5]]; but it nice to have it here. It is as slow as using new SequencePosition ;) $\endgroup$
    – garej
    Commented Jan 23, 2016 at 22:00
3
$\begingroup$ 
SplitBy[Transpose[{m1, Range@Length@m1}], First][[;; , ;; , -1]]

or

m2 = Range@Length@m1;
i = 1; Split[m2, m1[[j = i++]] === m1[[j + 1]] &]
Improve this answer
$\endgroup$
3
  • $\begingroup$ thank you, {14., 99530} for the first method, but I cannot check the second one. $\endgroup$
    – garej
    Commented Jan 24, 2016 at 18:41
  • $\begingroup$ you can check it like this Module[{m2 = Range@Length@m1,i=1},Split[m2, m1[[j = i++]] === m1[[j + 1]] &]] $\endgroup$
    – Basheer Algohi
    Commented Jan 24, 2016 at 18:44
  • $\begingroup$ {24., 99496} in my machine , that is too long !!! ):- $\endgroup$
    – Basheer Algohi
    Commented Jan 24, 2016 at 18:49
3
$\begingroup$

Just wanted to belatedly add a new-style spin on Kuba's classic old-style answer, using the "Counter" DataStructure

With[{counter = CreateDataStructure["Counter", 1]},
 Map[counter["Increment"] &, Split[m1], {2}]]
(* {{1, 2}, {3}, {4}, {5, 6}, {7, 8, 9}} *)
Improve this answer
$\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.