如何理解以下实现算法的 C# linq 代码 return 来自 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 的惊人连载 post：

基本上，如果我们有 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（结果集的总数等于 Binomial coefficient 从 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
Type: System.Func<TSource, Int32, IEnumerable<TResult>>
A transform function to apply to each source element;
the second parameter of the function represents the index of the source element.

Answer 2

我的nonelinq版本，应该是正确的！

测试结果：

Linq 风格：

我的方式：

我的代码

    /// <summary>
    /// Get the full combinations of k elements from a given list.
    /// </summary>
    public static List<List<T>> MyCombinations<T>(this List<T> elements, int k)
    {
        int n = elements.Count;
        //Given the same sequence, what if we wish to choose none of them? There does exist a subsequence which has zero elements, so we should produce it; the answer would be { { } }
        if (k == 0)
        {
            return new List<List<T>> {new List<T> {}};
        }
        if (k == n)
        {
            return new List<List<T>> {elements};
        }
        // What if we have a sequence of five items and we wish to choose six of them? There is no way to do that; there is no six-element subsequence. So the answer should be { }, the empty sequence of sequences
        if (k > n)
        {
            return new List<List<T>> {};
        }
        var result = new List<List<T>> {};
        for (int i = 0; i < n; i++)
        {
            T cur = elements[i];
            var rest = elements.Skip(i + 1).ToList();//take out current elment to fetch combinations of the rest set
            var combinationsOfRest = MyCombinations<T>(rest, k - 1);
            var currentList = new List<T> {cur};
            foreach (List<T> combination in combinationsOfRest)
            {
                result.Add(currentList.Concat(combination).ToList());
                //combination.Add(cur);
                //result.Add(combination);
            }
        }
        return result;
    }

如何理解以下实现算法的 C# linq 代码 return 来自 n 的 k 个元素的所有组合

How to understand the following C# linq code of implementing the algorithm to return all combinations of k elements from n

.net

c#

linq

recursion

combinatorics