C＃：如何遍历具有许多条件（过滤器和项目组）的列表 [英] C#: How to iterate over a list with many conditions (filters and groups of items)

问题描述

假设我有以下整数列表：

Let's say I have this list of ints:

var numbers = new List<int> { 0, 0, 0, 27, 29, 24, 35, 33, 32, 1, 1, 1, 22, 55,
    44, 44, 55, 59, 0, 0, 0, 0 };

我想实现以下描述的搜索算法。我正在寻找数字59。

I want to implement the search algorithm described below. I am looking for the number 59.

1. 某些未指定的条件决定了我是从左侧还是从右侧进行迭代。在此示例中，假设从左到右是迭代的方向。


2. 我们需要修剪列表的开头：
   
   
   
   
   • 2.1。前导0应该忽略。
   
   
   • 2.2。如果下一项具有相同的十位数，则将它们分组在一起。例如，将27、29、24分组在一起。接下来，将35、33、32分组在一起。接下来，55.等等。
   
   
   • 2.3。如果该组包含一个偶数，它将被忽略，然后继续进行下一个直到找到仅包含奇数的一个。该组也将被忽略，我们继续执行此算法的第3步。
   
   
   • 2.3。 1也将被忽略。
   
   

1. Some unspecified condition determines if I iterate from the left or from the right. In this example, let's say left to right is the direction of the iteration.
2. We need to trim the start of the list:
   • 2.1. Leading 0s should be ignored.
   • 2.2. The next items are grouped together if they have the same tens. For example, 27, 29, 24 are grouped together. Next, 35, 33, 32 are grouped together. Next, 55. Etc.
   • 2.3. If the group contains an even number, it is ignored and we move on to the next until we find one that contains only odd numbers. This group is ignored as well and we move on to step 3 of this algorithm.
   • 2.3. 1s are ignored as well.

• 3.1。我们正在寻找第一个包含以9结尾的项目的组。我们返回该项目。返回59。如果我们从另一个方向进行迭代，则会发现29个。

如何我将如何在C＃中实现此算法？这些是我的一些担忧：

How would I go about implementing this algorithm in C#? These are some of my concerns:

• 我可以在 或 for 构造，但是有时我不得不从列表的末尾开始的事实将导致索引混乱。我曾考虑过实现自定义 IEnumerable / IEnumerator 来掩盖这种混乱，但是在这种情况下，我应该使用 foreach 声明。但是，当我尝试处理上述 foreach 中的上述组时，我仍然会感到一团糟。


• 我应该如何遍历列表并同时建立这些组。


• 出于效率原因，我们不应该做第一遍从列表中过滤掉所有0的干净方法。在示例中，列表可以是一个非常长的10000000000元素列表的开始。如果我们要查找的数字是第15，则无需检查第9918477个元素。


• 此外，此算法有2个不同的部分（序列的开头和结尾） ）。我不知道应该如何在一次迭代中处理它们。

• I could iterate the whole list with a while or for construct, but the fact that sometimes I will have to start from the end of the list will lead to a messy code with the indexes. I have thought of implementing a custom IEnumerable/IEnumerator to hide this mess, but in this case, I should use a foreach statement. However, I think I will still have a mess when I try to handle the groups described above in this foreach.
• How should I iterate the list and build those groups at the same time. What is a clean way to do this in C#?
• For efficiency reasons, we should not do a first pass to filter out all 0s from the list. In the example, the list could be the start of a very long list of 10000000000 elements. There is no need to check the 9918477th element if the number we are looking for is the 15th.
• Also, there are 2 distinct parts to this algorithm (the start of the sequence and the end). I don't know how I should handle them both in one iteration.

注意：此示例不是家庭作业。这是一个简化的问题，旨在消除涉及复杂对象和条件的实际问题的不必要的细节。

Note: This example is not an homework. This is a simplified problem meant to remove the unnecessary details of the real problem that involves complex objects and conditions.

推荐答案

如果您熟悉LINQ，这很容易，并且熟悉编写非内置的LINQ方法。

This problem is quite easy if you are familiar with LINQ, and you are comfortable with writing LINQ methods that are not built in.

using System.Linq;

var source = new List<int> { 0, 0, 0, 27, 29, 24, 35, 33, 32, 1, 1, 1,
    22, 55, 44, 44, 55, 59, 0, 0, 0, 0 };

var result = source
    .SkipWhile(n => n == 0) // Leading 0s ignored
    .GroupConsecutiveByKey(n => n / 10) // Next items having same tens grouped
    .SkipWhile(g => g.Any(n => n % 2 == 0)) // Group containing an even number ignored
    .Skip(1) // Next group ignored
    .Where(g => !g.All(n => n == 1)) // 1s are ignored as well
    .FirstOrDefault(g => g.Any(n => n % 10 == 9)) // Contains item ending in 9
    .FirstOrDefault(n => n % 10 == 9); // Item ending in 9

Console.WriteLine($"Result: {result}");

输出：

结果：59

Result: 59

唯一缺少的方法是 GroupConsecutiveByKey 。这是一个实现：

The only missing method is the GroupConsecutiveByKey. Here is an implementation:

public static IEnumerable<List<TSource>> GroupConsecutiveByKey<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
    var comparer = EqualityComparer<TKey>.Default;
    TKey prevKey = default;
    List<TSource> list = null;
    foreach (var item in source)
    {
        var key = keySelector(item);
        if (list == null)
        {
            list = new List<TSource>();
        }
        else if (!comparer.Equals(key, prevKey))
        {
            yield return list;
            list = new List<TSource>();
        }
        list.Add(item);
        prevKey = key;
    }
    if (list != null) yield return list;
}

源序列仅被枚举一次。唯一的缓冲元素是属于一组连续的具有相同十进制数字的元素。该查询可以给出具有天文数的元素序列的结果。

The source sequence is enumerated only once. The only buffered elements are the ones belonging in a single group of consecutive numbers having same tens. This query could give a result for sequences with astronomical number of elements.

这篇关于C＃：如何遍历具有许多条件（过滤器和项目组）的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！