2
$\begingroup$

This question already has an answer here:

Im a trying to split a sorted 1D list of integers by sets of consecutives integers. The keywords in the question didn't trigger the answers I was looking for so I ask the question, no matter how trivial it looks like...

I just want for instance transform a list like:

   pts= {915, 916, 917, 1324, 1325, 1326, 2070, 2071, 2072, 2073, 2817, 2818, 2819, 2820, 3568, 3569, 3570}

Into a list like:

   {{915, 916, 917}, {1324, 1325, 1326}, {2070, 2071, 2072, 2073}, {2817,
   2818, 2819, 2820}, {3568, 3569, 3570}}

I tried FindClusters[ ] but could not tune the classification function fine enough and kept finding some cases where sets differing by a small difference where grouped together. I tried also similar global operators Gather[]but I always found some specific cases where sets were not correct.

So, swallowing my pride, I went to a procedural program:

clusterize[pts_] := Module[{j = 1, c = {}, b},
  While[j <= Length[pts],
    b = {pts[[j]]};
    Do[If[pts[[i + 1]] - pts[[i]] == 1, AppendTo[b, pts[[i + 1]]], 
     j = i; Break[]], {i, j, Length[pts] - 1}]; AppendTo[c, b]; 
   j = j + 1;]; Return[c]]

But this is not satisfactory, I keep finding idiotic cases like:

pts= {915, 916, 917, 1324, 1325, 1326, 2070, 2071, 2072, 2073, 2817, 2818,2819, 2820, 3568, 3569, 3570}

Gives:

In[27]:= clusterize[pts]

Out[27]= {{915, 916, 917}, {1324, 1325, 1326}, {2070, 2071, 2072, 
  2073}, {2817, 2818, 2819, 2820}, {3568, 3569, 3570}, {3569, 
  3570}, {3570}}

So can someone help me to find the bug in my procedural programming or much better a functionnal programming way to do the trick (or with patterns) ?

$\endgroup$

marked as duplicate by march, Feyre, Young, m_goldberg, user31159 Sep 2 '16 at 22:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Can you explain what is wrong with Gather? Split is older than Gather and what I show in my answer is exactly how we implemented Gather-like functionality before Gather was introduced. If my answer works, so should Gather and vice versa ... $\endgroup$ – Szabolcs Sep 2 '16 at 12:21
  • $\begingroup$ As for searching for duplicate posts: I don't use the search functionality within SE but rather just google for relevant posts. I found the above proposed duplicate by googling "mathematica stack exchange split list by consecutive integers". $\endgroup$ – march Sep 2 '16 at 16:03
  • $\begingroup$ Just a note, if you tried something, and it didn't work on all lists, use a list as example in which it doesn't work, because in the example list FindClusters[] does work. $\endgroup$ – Feyre Sep 2 '16 at 16:29
3
$\begingroup$

How about Split?

Split[Sort[pts], Abs[#1 - #2] <= 1 &]

I haven't looked at performance though.

$\endgroup$
  • $\begingroup$ In the OP the numbers are already sorted. However, since you additionally included Sort in your solution I thought of being picky and trying to find a case where it does not work. For pts = {1, 2, 4, 2, 3, 3, 3} we get {{1, 2, 2, 3, 3, 3, 4}} although I would expect {{1, 2}, {4}, {2, 3, 3, 3}}. $\endgroup$ – yarchik Sep 2 '16 at 13:05
  • $\begingroup$ @Szabolcs: thanks this is exactly what I wanted. It works well!I tried also the same syntax with Gather and it returns only pairs. And GatherBy with the same syntax and function return errors $\endgroup$ – Christian Néel Sep 2 '16 at 13:08
2
$\begingroup$

(Edited to employ Differences)

@Szabolcs's aswer is pretty much perfect, but let my add my procedural solution:

clusterize[pts_] := Module[{diffs, pos},
  diffs = Differences[pts];
  pos = Append[Prepend[Flatten@Position[diffs, x_ /; x > 1] + 1, 1], Length@pts + 1];
  Table[
   Table[pts[[i]], {i, pos[[j]], pos[[j + 1]] - 1}]
   , {j, 1, Length@pos - 1}]
  ]

Let's append one more value to the initial list to show that clusterize is functional:

pts = {915, 916, 917, 1324, 1325, 1326, 2070, 2071, 2072, 2073, 2817, 2818, 2819, 2820, 3568, 3569, 3570, 4000};

Thence

clusterize[pts]

gives

{{915, 916, 917}, {1324, 1325, 1326}, {2070, 2071, 2072, 2073}, {2817, 2818, 2819, 2820}, {3568, 3569, 3570}, {4000}}

If you have repeating values, e.g. pts={...,4000,4000}, both @Szabolcs's and my answer will give {...,{4000,4000}}. If you don't want them in the output, then maybe use Map[DeleteDuplicates, clusterize[pts]].


EDIT: Machine Learning

It might appear that FindClusters should be a natural choice for such a problem:

FindClusters[pts]

{{915, 916, 917, 1324, 1325, 1326, 2070, 2071, 2072, 2073, 2817, 2818, 2819, 2820, 3568, 3569, 3570, 4000}}

but it fails. Maybe with some DistanceFunction:

FindClusters[pts, DistanceFunction -> ManhattanDistance]

{{915, 916, 917}, {1324, 1325, 1326}, {2070, 2071, 2072, 2073}, {2817, 2818, 2819, 2820}, {3568, 3569, 3570, 4000}}

Better, but 4000 should be in a separate group (other DistanceFunctions don't work either). Even specifying the number of clusters explicitly fails:

FindClusters[pts, 6]

{{915, 916, 917}, {1324, 1325, 1326}, {2070, 2071}, {2072, 2073}, {2817, 2818, 2819, 2820}, {3568, 3569, 3570, 4000}}

(Note: the above two methods happen to work when 4000 is deleted from pts.)

So maybe some classification?

c = ClusterClassify[pts]

Method: DBSCAN

Number of classes: 6

Looks promising;

GatherBy[pts, c]

{{915, 916, 917}, {1324, 1325, 1326}, {2070, 2071, 2072, 2073}, {2817, 2818, 2819, 2820}, {3568, 3569, 3570}, {4000}}

Correct! Is it general enough?

pts2 = {1, 2, 3, 5, 6, 8, 10, 11, 13};
c = ClusterClassify[pts2]
GatherBy[pts2, c]

{{1, 2, 3, 5, 6, 8, 10, 11, 13}}

It fails miserably. But wait, in the case of pts Method: DBSCAN was used automatically. Maybe:

c = ClusterClassify[pts2, Method -> "DBSCAN"]
GatherBy[pts2, c]

{{1, 2, 3}, {5, 6}, {8}, {10, 11}, {13}}

Correct! Works also for {1, 2, 4, 5}, {1, 3, 4, 5}, {1, 2, 3, 5}, {1, 2, 5} and {1, 4, 5}. Unfortunately, it fails for {1, 3, 5} or {1, 2, 4}. Nevertheless, it seems to work for a number of situations.

$\endgroup$
  • $\begingroup$ Some tips: Differences is useful. To exact a range, consider Part and Span, as in array[[i;;j]]. $\endgroup$ – Szabolcs Sep 2 '16 at 12:43
  • $\begingroup$ @corey979: thanks for taking the time to do this, It seems to work well, I will test it further with new data. I am personnaly very rusted in procedural programming!... $\endgroup$ – Christian Néel Sep 2 '16 at 13:13
  • $\begingroup$ ChristianNéel Thanks, but @Szabolcs answer is much better; I'd recommend to stick to that one and treat mine maybe as a reference for future issues. $\endgroup$ – corey979 Sep 2 '16 at 13:25

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