检测给定列表中至少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

我觉得你应该做的第一件事是订购清单.然后只需要走过它,记住当前序列的长度并检测它何时结束.说实话,我怀疑一个简单的foreach循环将是最简单的方法 - 我不能立即想到任何奇妙的LINQ类似的方法.如果你真的想要,你当然可以在迭代器块中执行它,但请记住,从列表开始排序意味着你有一个合理的"预先"成本.所以我的解决方案看起来像这样:

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-ish的做事方式.我现在没有时间全面实施它,但是:

• 订购序列
• 使用类似SelectWithPrevious(可能更好的命名SelectConsecutive)的东西来获得连续的元素对
• 使用包含索引的Select的重载来获取元组(索引,当前,前一个)
• 过滤掉(current = previous + 1)的任何项目,以获得计算为序列开始的任何位置(特殊情况索引= 0)
• SelectWithPrevious在结果上使用以获得两个起点之间的序列长度(从前一个减去一个索引)
• 过滤掉长度小于3的任何序列

我怀疑你需要int.MinValue在有序序列上连续,以保证最终项目正确使用.

编辑:好的,我实现了这一点.这是关于我能想到的LINQiest方法...我使用null值作为"sentinel"值来强制开始和结束序列 - 有关更多详细信息,请参阅注释.

总的来说,我不推荐这个解决方案.很难让你的头脑清醒,虽然我有理由相信这是正确的,但我花了一段时间考虑可能的一对一错误等.这是一个有趣的旅程,你可以用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));
    }
}

Answer 2

Jon Skeet的/ Timwi的解决方案是可行的方法.

为了好玩,这是一个完成工作的LINQ查询(非常低效):

var sequences = input.Distinct()
                     .GroupBy(num => Enumerable.Range(num, int.MaxValue - num + 1)
                                               .TakeWhile(input.Contains)
                                               .Last())  //use the last member of the consecutive sequence as the key
                     .Where(seq => seq.Count() >= 3)
                     .Select(seq => seq.OrderBy(num => num)); // not necessary unless ordering is desirable inside each sequence.

通过将输入加载到HashSet(改进Contains)中可以略微提高查询的性能,但这仍然不会产生任何接近有效的解决方案.

我所知道的唯一错误是如果序列包含大数量的负数(我们不能代表count参数Range),则算术溢出的可能性.使用自定义static IEnumerable<int> To(this int start, int end)扩展方法很容易解决这个问题.如果有人能想到任何其他避免溢出的简单技术,请告诉我.

编辑:这是一个稍微冗长(但同样效率低)的变种,没有溢出问题.

var sequences = input.GroupBy(num => input.Where(candidate => candidate >= num)
                                          .OrderBy(candidate => candidate)
                                          .TakeWhile((candidate, index) => candidate == num + index)
                                          .Last())
                     .Where(seq => seq.Count() >= 3)
                     .Select(seq => seq.OrderBy(num => num));