如何理解以下C＃ LINQ代码，以实现从n个元素中返回k个元素的所有组合算法

Question

如何理解以下C＃ LINQ代码，以实现从n个元素中返回k个元素的所有组合算法

9

能否有人详细解释一下这段代码，或者给出一个非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)));
}

- xuehui

这将取决于“Combinations”如何定义，而您尚未显示。它不是标准的LINQ方法。 - Asad Saeeduddin

3

@Asad 这是一个递归方法。 - Gert Arnold

@GertArnold 哦，傻了。 - Asad Saeeduddin

如果“elements”被延迟加载，性能将非常糟糕！ - Lukazoid

2个回答

0

我的非Linq版本应该是正确的！

测试结果：

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;
    }

- xuehui

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- VMAtm · Accepted Answer

这段代码最好的理解方式是阅读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>>
要应用于每个源元素的转换函数；
函数的第二个参数表示源元素的索引。