递归获取 IEnumerable 组合的说明

本文关键字：说明 组合 IEnumerable 获取 递归 | 更新日期: 2023-09-27 18:34:56

我最近在这里看到了彭扬写的以下代码片段：查找数组中所有项目组合的最佳方法是什么？

static IEnumerable<IEnumerable<T>>
    GetKCombs<T>(IEnumerable<T> list, int length) where T : IComparable
{
    if (length == 1) return list.Select(t => new T[] { t });
    return GetKCombs(list, length - 1)
        .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) > 0), 
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

使用列表 { 1， 2， 3， 4 } 和长度为 2 调用 GetKCombs 将返回：

{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}

代码运行良好，但我不明白这段代码是如何以及为什么工作的，如果有人能向我解释一下，我将不胜感激。

递归获取 IEnumerable 组合的说明

一般来说，递归方法的作用是它首先将输入列表减少到单元素数组数组中(退出条件(，然后递归地将 1 个元素添加到每个单元素数组数组中，使结果变成 2 元素数组的数组，并连续重复添加 1 个元素，直到元素数组中的元素数量成为您需要的长度， 加法的一个条件是数组中的最后一个元素小于从输入列表添加到数组中的元素。:)

(我知道它比以前更令人困惑.递归LINQ就是这样做的(

所以让我们以你为例。

list = { 1, 2, 3, 4 }  // IEnumerable<int>, T => int
length = 2

如果你注意到 GetKCombs 方法，它是递归的，直到你达到长度 == 1 的条件。

因此，当您传入长度 = 2 时，您实际上是在这样做：

return list.Select(t => new T[] { t }) // we substituted the call for length = 1
        .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) > 0), 
            (t1, t2) => t1.Concat(new T[] { t2 }));

list.Select(t => new T[] { t })基本上返回一个元素数组，其中元素本身就是一个 1 元素数组。即输入列表中的每个元素。

{ {1}, {2}, {3}, {4} }

以此为基数，再次为输入列表中的每个元素，大于基数结果的每个元素，{1, 2, 3, 4}我们创建对

。

即对于输入中的 1，我们将匹配基数中的 2,3,4。 对于 2，我们将匹配 3 和 4。对于 3，我们将匹配 4这就是什么

list.Where(o => o.CompareTo(t.Last()) > 0

确实如此。

一旦我们找到这对{1}和{2, 3, 4}，我们就通过在 Select 查询中连接它们来创建 2 个项目元组。 (t1, t2) => t1.Concat(new T[] { t2 })以获取结果集。

{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}

这成为我们的新基地。

因为我们的输入长度 = 2，所以我们停在这里。

但是如果长度是 3，那么有了这个底座，我们将再次运行，并发现对于基{1,2}输入列表中的元素中的第一个元素，大于第一个元素(2 in {1, 2})中的最后一个将是 3 和 4。

所以我们会有 2 个元组。 {1,2,3} and {1,2,4}同样，我们会{1,3,4} 同样，我们会{2,3,4}

您可以看到基中最后一个元素为 4 的元素是如何被消除的。

这个过程会重复，直到得到我们想要的元组大小。

相关文章：