将列表拆分<int>为一组连续的数字

Question

我有一个排序List<int>，比如{ 1, 2, 3, 4, 6, 7, 9 }
我想把它分成几组——每个组都有这样的连续数字：{ {1, 2, 3, 4}, {6, 7}, {9} }

我知道我可以使用for循环遍历列表，并在当前值和先前值之间进行比较，然后决定是附加到最后一个组还是创建新组。但我想找到一种"漂亮"的方式来做到这一点。也许使用 LINQ？

编辑：

我从项目more-itertools中找到了一个python代码：

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)

Answer 1

这是取自 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;
}

你可以像这样使用它：

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

发布 C# 7 后，通过使用Span来避免创建新列表，可以提高效率。

---

此更新版本无需分配任何列表即可完成此操作。

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);
        }
    }
}

Answer 2

这是我对使用迭代器的扩展方法的建议：

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);
    }
}

我必须说Python算法非常令人印象深刻，这是它的C#实现：

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);
}

下面是 Python 算法的 C# 单行实现：

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

注意：启用了可为空的批注上下文的 C# 8 应在两种 Python 方法中使用Func<int,int>?。您还可以使用??=来分配ordering。

Answer 3

@Bradley Uffner 和 @NetMage 非分配迭代器方法的正确实现是这样的：

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);
        }
    }
}

即使对于无序输入，它也能正常工作，只迭代源序列一次，并正确处理所有极端情况和整数溢出/下溢。它失败的唯一情况是连续范围计数大于 int.MaxValue 。

但是看看你的后续问题，可能以下实现会更好地满足你的需求：

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);
        }
    }
}

Answer 4

尝试以下代码;

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