这段代码最好的理解方式是阅读Eric Lippert的系列文章:
基本上,如果我们有一个包含5个项的IEnumerable,并想要获得所有大小为3的组合,我们需要生成类似于以下内容的东西:
{
// 50, 60, 70, 80, 90
{50, 60, 70}, // T T T F F
{50, 60, 80}, // T T F T F
{50, 60, 90}, // T T F F T
{50, 70, 80}, // T F T T F
{50, 70, 90}, // T F T F T
{50, 80, 90}, // T F F T T
{60, 70, 80}, // F T T T F
{60, 70, 90}, // F T T F T
{60, 80, 90}, // F T F T T
{70, 80, 90} // F F T T T
}
Eric的递归实现:
// Takes integers n and k, both non-negative.
// Produces all sets of exactly k elements consisting only of
// integers from 0 through n - 1.
private static IEnumerable<TinySet> Combinations(int n, int k)
{
// Base case: if k is zero then there can be only one set
// regardless of the value of n: the empty set is the only set
// with zero elements.
if (k == 0)
{
yield return TinySet.Empty;
yield break;
}
// Base case: if n < k then there can be no set of exactly
// k elements containing values from 0 to n - 1, because sets
// do not contain repeated elements.
if (n < k)
yield break;
// A set containing k elements where each is an integer from
// 0 to n - 2 is also a set of k elements where each is an
// integer from 0 to n - 1, so yield all of those.
foreach(var r in Combinations(n-1, k))
yield return r;
// If we add n - 1 to all the sets of k - 1 elements where each
// is an integer from 0 to n - 2, then we get a set of k elements
// where each is an integer from 0 to n - 1.
foreach(var r in Combinations(n-1, k-1))
yield return r.Add(n-1);
}
在您的情况下,代码工作方式如下:
return k == 0
// if we are done, return empty array
? new[] {new T[0]}
// for each element and each number from 0 to enumerable size
: elements.SelectMany((e, i) =>
elements
//skip first i elements, as we already produced combination with them
.Skip(i + 1)
//get all the combinations with size k - 1
.Combinations(k - 1)
//add current element to all produced combinations
.Select(c => (new[] {e}).Concat(c)));
这段非递归代码将会非常庞大和难以阅读,试着理解递归:
假设我们有一个5个元素的 IEnumerable
: {16, 13, 2, 4, 100}
,我们需要从中取出大小为2的所有组合(结果集的总数等于从5到2的二项式系数 = 5! / (2! * 3!) = 10)
你的代码将会产生:
- 对于
16
,我们需要从第二个位置开始获取所有大小为 1
的组合:
- 对于元素
13
,我们需要从第三个位置开始获取所有大小为 0
的组合
- 第一个结果:
{16, 13}
- 跳过
13
,对于元素 2
,我们需要从第四个位置开始获取所有大小为 0
的组合
- 第二个结果:
{16, 2}
- 跳过
13, 2
,对于元素 4
,我们需要从第五个位置开始获取所有大小为 0
的组合
- 第三个结果:
{16, 4}
- 跳过
13, 2, 4
,对于元素 100
,我们需要从第六个位置开始获取所有大小为 0
的组合
- 第四个结果:
{16, 100}
- ... 重复以上步骤,从
13
,2
,4
开始:
{13, 2}
,{13, 4}
,{13, 100}
,{2, 4}
,{2, 100}
,{4, 100}
这样我们就得到了所有10个所需的组合。代码作者使用的是这个方法的重载:Enumerable.SelectMany<TSource, TResult> Method (IEnumerable<TSource>, Func<TSource, Int32, IEnumerable<TResult>>)
:
selector
类型: System.Func<TSource, Int32, IEnumerable<TResult>>
要应用于每个源元素的转换函数;
函数的第二个参数表示源元素的索引。