将一个 List<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)

- PM Extra

---

“to some slice”是什么意思？从一个包含1个元素的集合如何得到包含3个不同元素数量的集合，这一点不太清楚。 - itsme86

为什么for循环不够"优雅"? 我的猜测是，使用Linq解决方案可能会更"丑陋"。 - juharr

编程的目标是写漂亮的代码还是高质量的代码？如果你遇到需要循环的问题，没有什么比循环更好的了。 - maccettura

对不起，我的英语很糟糕... - PM Extra

我很难理解为什么这个问题因为“基于观点”而被投了那么多关闭票。我认为很明显，大多数人似乎对“pretty”这个词感到困惑，是由于不熟悉英语语言，而并非字面意思。 - Bradley Uffner

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

- Bradley Uffner

---

但是 @BradleyUffner，这里有一个循环，看起来不太好！/s - maccettura

用计数并返回 Enumerable.Range 是否比返回列表更容易呢？ - Joey

@BradleyUffner：我其实还没有运行这段代码，但是看起来现在非常不错。 - Eric Lippert

@BradleyUffner 初始化 count = 1；将 last = startNumber；在 list.Skip(1) 上使用 foreach 循环；测试 i-last == 1，避免任何下溢/上溢的数学计算。哦，还有将顶部测试反转为 if (list.Any())，你就不需要 yield break。 - NetMage

所有这些都让我希望有一个“整数”类型的通用约束，这样就可以适用于int、byte、long等类型，而无需为每种类型制作一个版本。 - Bradley Uffner

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

这是一个使用C#一行代码实现Python算法的示例：

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。

- NetMage

---

C# 迭代器方法陷入了延迟执行的陷阱。尝试使用 var result = input.GroupConsecutive().ToList()，你会看到结果。虽然我认为利用 GetEnumerator 的实现是正确的方式，但当前的实现方式是错误的。过于关注简洁性而不是功能性。毕竟，重要的是拥有自定义扩展方法，以允许简洁的使用，而不是简洁的实现。 - Ivan Stoev

@IvanStoev 有趣的是，LINQPad的Dump()可以工作，而ToList()却不行... 我不确定是否能够在不需要额外存储的情况下修复它 :( - NetMage

我改变了我的答案，使用 ToList 来保存子序列 :( - NetMage

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

- Ivan Stoev

---

也许你可以使用 long 作为计数，自己编写 RangeIterator 的版本来解决这个问题？像这样：static IEnumerable<int> RangeIterator(int start, long count) { count += start; for (int i = start; i < count; i++) yield return i; } - NetMage

@NetMage 确实如此！但我刚意识到这个方法可以简单地产生范围，然后（如果需要）可以使用简单的“Select”和标准/建议的自定义“RangeIterator”轻松地将其转换为序列。 - Ivan Stoev

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

- lucky

---

如果source中没有任何项，它会抛出一个异常（我在我的代码中也曾经遇到过同样的问题）。 - Bradley Uffner

@Bradley Uffner，谢谢提醒。 - lucky