12

I have a sorted List<int> like { 1, 2, 3, 4, 6, 7, 9 }
I want to split that into some groups -- every group has consecutive number like this: { {1, 2, 3, 4}, {6, 7}, {9} }

I know I can use for loop to traverse the list, and compare between the current value and previous value, then decide whether append to last group or create a new group. But I want to find a "pretty" way to do it. Maybe use LINQ?

Edit:

I found a python code from project more-itertools:

def consecutive_groups(iterable, ordering=lambda x: x): for k, g in groupby( enumerate(iterable), key=lambda x: x[0] - ordering(x[1]) ): yield map(itemgetter(1), g)
Improve this question
8
  • What do you mean by "to some slice"? It's unclear how you get from 1 collection to 3 collections with different numbers of elements. Commented Jan 22, 2018 at 17:57
  • @itsme86 I had the same question until I read "consecutive number" Commented Jan 22, 2018 at 17:58
  • 8
    Why wouldn't a for loop be "pretty"? My guess is that a Linq solution would actually be "uglier" IMHO. Commented Jan 22, 2018 at 17:59
  • 1
    Is the goal of programming to write pretty code or quality code? If you encounter a problem where you need to loop, nothing beats a loop. Commented Jan 22, 2018 at 18:01
  • 1
    I have a hard time understanding why this question is getting so many close votes for being "opinion based". I think it seems fairly clear that the word "pretty", that most people seem to be taking such issues with, was used due being unfamiliar with the English language, and was not meant to be taken literally. Commented Jan 22, 2018 at 21:50

4 Answers 4

Reset to default
9

Here is an extension method taken from http://bugsquash.blogspot.com/2010/01/grouping-consecutive-integers-in-c.html

public static IEnumerable<IEnumerable<int>> GroupConsecutive(this IEnumerable<int> list) { var group = new List<int>(); foreach (var i in list) { if (group.Count == 0 || i - group[group.Count - 1] <= 1) group.Add(i); else { yield return group; group = new List<int> {i}; } } yield return group; }

You can use it like this:

var numbers = new[] { 1, 2, 3, 4, 6, 7, 9 }; var groups = numbers.GroupConsecutive();

Once C# 7 is released, this can made even more efficient with the use of Span to avoid creating new lists.

This updated version does it without allocating any lists.

public static class EnumerableExtensions { public static IEnumerable<IEnumerable<int>> GroupConsecutive(this IEnumerable<int> list) { if (list.Any()) { var count = 1; var startNumber = list.First(); int last = startNumber; foreach (var i in list.Skip(1)) { if (i < last) { throw new ArgumentException($"List is not sorted.", nameof(list)); } if (i - last == 1) count += 1; else { yield return Enumerable.Range(startNumber, count); startNumber = i; count = 1; } last = i; } yield return Enumerable.Range(startNumber, count); } } }
Improve this answer
Sign up to request clarification or add additional context in comments.

29 Comments

But @BradleyUffner, this has a loop, its not pretty! /s
Wouldn't it be easier to count and return Enumerable.Range instead of a list?
Nice solution. Challenge: can you do it without allocating any lists without using Span?
Not fixed. First: you need a yield break in there. Second: Count() is inefficient if the sequence is not a collection. You don't need to count all the pennies in a jar to tell if there are more than zero. Use Any to check if there is at least one element in a sequence. Third: why is the result of an empty list to produce a sequence that contains one empty sequence? I would have thought that the result would be a sequence containing zero sequences.
@BradleyUffner: I haven't actually, you know, run the code, but yes that looks pretty good now.
|
8

Here is my suggestion for an extension method using iterators:

public static IEnumerable<IEnumerable<int>> GroupConsecutive(this IEnumerable<int> src) { var more = false; // compiler can't figure out more is assigned before use IEnumerable<int> ConsecutiveSequence(IEnumerator<int> csi) { int prevCurrent; do yield return (prevCurrent = csi.Current); while ((more = csi.MoveNext()) && csi.Current-prevCurrent == 1); } var si = src.GetEnumerator(); if (si.MoveNext()) { do // have to process to compute outside level yield return ConsecutiveSequence(si).ToList(); while (more); } }

I must say the Python algorithm is very impressive, here is a C# implementation of it:

public static IEnumerable<IEnumerable<int>> GroupConsecutive(this IEnumerable<int> iterable, Func<int,int> ordering = null) { ordering = ordering ?? (n => n); foreach (var tg in iterable .Select((e, i) => (e, i)) .GroupBy(t => t.i - ordering(t.e))) yield return tg.Select(t => t.e); }

Here is a C# one-line implementation of the Python algorithm:

public static IEnumerable<IEnumerable<int>> GroupConsecutive(this IEnumerable<int> iterable, Func<int,int> ordering = null) => iterable .Select((e, i) => (e, i)) .GroupBy( t => t.i - (ordering ?? (n => n))(t.e), (k,tg) => tg.Select(t => t.e));

NOTE: C# 8 with nullable annotation context enabled should use Func<int,int>? in both Python methods. You could also use ??= to assign ordering.

Improve this answer

3 Comments

The C# iterator method is falling into deferred execution trap. Try var result = input.GroupConsecutive().ToList() and you'll see. While I believe implementation utilizing the GetEnumerator is the right way to go, the current implementation is just wrong. Putting too much attention on conciseness rather then on the functionality. After all, it's important to have a custom extension method, to allow concise usage, not concise implementation.
@IvanStoev Interestingly LINQPad Dump() works where ToList() does not... I am not sure it is going to be possible to fix without requiring extra storage then :(
I changed my answer to use ToList to save the subsequences :(
3

The correct implementation of @Bradley Uffner and @NetMage non allocating iterator method is like this:

public static IEnumerable<IEnumerable<int>> GroupConsecutive(this IEnumerable<int> source) { using (var e = source.GetEnumerator()) { for (bool more = e.MoveNext(); more; ) { int first = e.Current, last = first, next; while ((more = e.MoveNext()) && (next = e.Current) > last && next - last == 1) last = next; yield return Enumerable.Range(first, last - first + 1); } } }

It works correctly even for unordered input, iterates the source sequence only once and handles correctly all corner cases and integer over/underflow. The only case it fails is for consecutive range count bigger than int.MaxValue.

But looking at your follow up question, probably the following implementation will better suit your needs:

public static IEnumerable<(int First, int Last)> ConsecutiveRanges(this IEnumerable<int> source) { using (var e = source.GetEnumerator()) { for (bool more = e.MoveNext(); more;) { int first = e.Current, last = first, next; while ((more = e.MoveNext()) && (next = e.Current) > last && next - last == 1) last = next; yield return (first, last); } } }
Improve this answer

2 Comments

Perhaps your own version of RangeIterator using long for count would fix that? Something like static IEnumerable<int> RangeIterator(int start, long count) { count += start; for (int i = start; i < count; i++) yield return i; }
@NetMage Indeed! But I just realized that the method can simply yield ranges, which then (if needed) can easily be turned into sequences with simple Select and standard/suggested custom RangeIterator.
0

Try the following code;

public static IEnumerable<IEnumerable<int>> GroupConsecutive(this IEnumerable<int> source) { if (!source.Any()) { yield break;} var prev = source.First(); var grouped = new List<int>(){ prev }; source = source.Skip(1); while (source.Any()) { var current = source.First(); if (current - prev != 1) { yield return grouped; grouped = new List<int>(); } grouped.Add(current); source = source.Skip(1); prev = current; } yield return grouped; } var numbers = new[] { 1, 2, 3, 4, 6, 7, 9 }; var result = numbers.GroupConsecutive(); Output 1,2,3,4 6,7 9
Improve this answer

2 Comments

It throws an exception if there are no items in source (I originally had the same problem in my code too).
@Bradley Uffner, thanks for reminding.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.