递归获取 IEnumerable 组合的说明

Question

我最近在这里看到了 Pengyang 写的以下代码片段： What is the best way to find all combinations of items in an array?

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 会 return:

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

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

Answer 1

总的来说递归方法的作用是先将输入列表缩减为单元素数组的数组（退出条件），然后递归地向单元素数组的每个数组中添加1个元素，使得结果变成一个2元素数组，并不断重复添加1个元素，直到元素数组中的元素数量成为您需要的长度，添加的一个条件是数组中的最后一个元素小于比从输入列表添加到数组的元素。 :)

（我知道它比以前更令人困惑。递归 LINQ 做到了）

让我们举个例子。

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

如果您注意到 GetKCombs 方法，它会递归直到您达到长度 == 1 条件..

所以当你传入 length = 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 }) 基本上 returns 一个元素数组，其中元素本身是一个 1 元素数组。即输入列表中的每个元素。

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

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

即对于输入中的 1，我们将匹配 base 中的 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 的基数中的元素是如何被消除的。

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

递归获取 IEnumerable 组合的说明

Explanation of getting combinations of IEnumerable recursively

c#

combinations