c# - 从给定列表中检测至少 3 个序列号的序列

Question

我有一个数字列表，例如21,4,7,9,12,22,17,8,2,20,23

我希望能够挑选出序列号的序列(长度至少为 3 项)，因此从上面的示例来看，它将是 7、8、9 和 20、21、22、23。

我玩过一些丑陋的庞大函数，但我想知道是否有一种简洁的 LINQ-ish 方法来做到这一点。

有什么建议吗？

更新:

非常感谢所有回复，非常感谢。我目前正在和他们一起玩，看看哪个最能融入我们的项目。

Answer 1

令我印象深刻的是，您应该做的第一件事就是订购 list 。然后只需遍历它，记住当前序列的长度并检测它何时结束。老实说，我怀疑一个简单的 foreach 循环将是最简单的实现方式——我无法立即想到任何非常简洁的类似 LINQ 的实现方式。如果您确实愿意，您当然可以在迭代器 block 中执行此操作，但请记住，对列表进行排序意味着无论如何您都有合理的“前期”成本。所以我的解决方案看起来像这样:

var ordered = list.OrderBy(x => x);
int count = 0;
int firstItem = 0; // Irrelevant to start with
foreach (int x in ordered)
{
    // First value in the ordered list: start of a sequence
    if (count == 0)
    {
        firstItem = x;
        count = 1;
    }
    // Skip duplicate values
    else if (x == firstItem + count - 1)
    {
        // No need to do anything
    }
    // New value contributes to sequence
    else if (x == firstItem + count)
    {
        count++;
    }
    // End of one sequence, start of another
    else
    {
        if (count >= 3)
        {
            Console.WriteLine("Found sequence of length {0} starting at {1}",
                              count, firstItem);
        }
        count = 1;
        firstItem = x;
    }
}
if (count >= 3)
{
    Console.WriteLine("Found sequence of length {0} starting at {1}",
                      count, firstItem);
}

编辑:好的，我刚刚想到了一种更像 LINQ 的做事方式。我现在没有时间完全实现它，但是:

• 排序顺序
• 使用像 SelectWithPrevious 这样的东西(最好命名为 SelectConsecutive)以获得连续的元素对
• 使用包含索引的 Select 重载来获取(索引、当前、上一个)的元组
• 过滤掉 (current = previous + 1) 的任何项目，以获取算作序列的开始的任何项目(特殊情况索引=0)
• 对结果使用SelectWithPrevious 得到两个起点之间序列的长度(从前一个索引减去一个索引)
• 过滤掉任何长度小于3的序列

我怀疑您需要在有序序列上连接 int.MinValue，以确保正确使用最终项目。

编辑:好的，我已经实现了。这是我能想到的 LINQiest 方法...我使用 null 值作为“哨兵”值来强制开始和结束序列 - 有关更多详细信息，请参阅评论。

总的来说，我不会推荐这个解决方案。很难让你头脑清醒，虽然我有理由相信它是正确的，但我花了一段时间思考可能的差一错误等。这是一次了解你可以做的事情的有趣旅程使用 LINQ...以及您可能不应该使用的内容。

哦，请注意，我已将“最小长度为 3”的部分推送给调用者 - 当您有这样的元组序列时，单独过滤掉它会更干净，IMO。

using System;
using System.Collections.Generic;
using System.Linq;

static class Extensions
{
    public static IEnumerable<TResult> SelectConsecutive<TSource, TResult>
        (this IEnumerable<TSource> source,
         Func<TSource, TSource, TResult> selector)
    {
        using (IEnumerator<TSource> iterator = source.GetEnumerator())
        {
           if (!iterator.MoveNext())
           {
               yield break;
           }
           TSource prev = iterator.Current;
           while (iterator.MoveNext())
           {
               TSource current = iterator.Current;
               yield return selector(prev, current);
               prev = current;
           }
        }
    }
}

class Test
{
    static void Main()
    {
        var list = new List<int> {  21,4,7,9,12,22,17,8,2,20,23 };

        foreach (var sequence in FindSequences(list).Where(x => x.Item1 >= 3))
        {
            Console.WriteLine("Found sequence of length {0} starting at {1}",
                              sequence.Item1, sequence.Item2);
        }
    }

    private static readonly int?[] End = { null };

    // Each tuple in the returned sequence is (length, first element)
    public static IEnumerable<Tuple<int, int>> FindSequences
         (IEnumerable<int> input)
    {
        // Use null values at the start and end of the ordered sequence
        // so that the first pair always starts a new sequence starting
        // with the lowest actual element, and the final pair always
        // starts a new one starting with null. That "sequence at the end"
        // is used to compute the length of the *real* final element.
        return End.Concat(input.OrderBy(x => x)
                               .Select(x => (int?) x))
                  .Concat(End)
                  // Work out consecutive pairs of items
                  .SelectConsecutive((x, y) => Tuple.Create(x, y))
                  // Remove duplicates
                  .Where(z => z.Item1 != z.Item2)
                  // Keep the index so we can tell sequence length
                  .Select((z, index) => new { z, index })
                  // Find sequence starting points
                  .Where(both => both.z.Item2 != both.z.Item1 + 1)
                  .SelectConsecutive((start1, start2) => 
                       Tuple.Create(start2.index - start1.index, 
                                    start1.z.Item2.Value));
    }
}