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

Question

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

Answer 1

How about Split?

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

I haven't looked at performance though.

Answer 2

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