如何理解以下C#linq代码实现该算法以返回n中k个元素的所有组合

Question

任何人都可以详细说明这段代码的一些细节,甚至可以给出这个算法的非Linq版本:

public static IEnumerable<IEnumerable<T>> Combinations<T>
    (this IEnumerable<T> elements, int k)
{
   return k == 0 ? new[] { new T[0] }
                 : elements.SelectMany(
                       (e, i) =>
                         elements
                         .Skip(i + 1)
                         .Combinations(k - 1)
                         .Select(c => (new[] {e}).Concat(c)));
}

Answer 1

理解这段代码的最好方法是阅读Eric Lippert的精彩系列文章:

• 制作组合,第一部分
• 制作组合,第二部分
• 制作组合,第三部分
• 制作组合,第四部分
• 制作组合,第五部分

基本上,如果我们有IEnumerable5个项目,并希望得到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(结果集的总数等于从2到2的二项式系数= 5! / (2! * 3!) = 10)

您的代码将生成:

1. 因为16我们需要所有尺寸的组合1,从第二个位置开始:
2. 对于元素,13我们需要0从第三个位置开始的所有大小组合
3. 第一个结果: { 16, 13 }
4. 跳过13,对于元素,2我们需要0从第四个位置开始的所有大小组合
5. 第二个结果: { 16, 2 }
6. 跳过13, 2,对于元素,4我们需要0从第五个位置开始的所有大小组合
7. 第三个结果: { 16, 4 }
8. 跳过13, 2, 4,对于元素,100我们需要0从第六个位置开始的所有大小组合
9. 第四个结果: { 16, 100 }
10. ...重复所有从上面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>>
应用于每个源元素的转换函数;
函数的第二个参数表示源元素的索引.