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)
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
.
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);
}
}
}
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);
}
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With