Split sorted list of integers by groups of consecutive integers [duplicate]

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

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

• 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 ... – Szabolcs Sep 2 '16 at 12:21
• 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". – march Sep 2 '16 at 16:03
• 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. – Feyre Sep 2 '16 at 16:29

How about Split?

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


I haven't looked at performance though.

• 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}}. – yarchik Sep 2 '16 at 13:05
• @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 – Christian Néel Sep 2 '16 at 13:08

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

• Some tips: Differences is useful. To exact a range, consider Part and Span, as in array[[i;;j]]. – Szabolcs Sep 2 '16 at 12:43
• @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!... – Christian Néel Sep 2 '16 at 13:13
• 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. – corey979 Sep 2 '16 at 13:25