C# 如何在递归调用期间使用 yield 运算符？

Question

我有一个构建数组组合的递归方法。该方法效果很好，但要求在迭代之前将结果数组完全分配到内存中。我了解了 yield 运算符，因为它使用的是 IEnumerator<> ，所以它似乎一次应该 return 一个结果，从而大大减少了内存消耗。我尝试了各种方案来 'yield' 结果。但是，其中 none 是成功的。我想知道如何使用 yield 运算符来达到预期的结果。

这是构建组合的代码：

public static class CombinationArray
{
    private static int _resultsIndex;
    private static int[][] _results;
    public static int GetBinCoeff(int n, int k)
    {
        int r = 1;
        int d;
        if (k > n) return 0;
        for (d = 1; d <= k; d++)
        {
            r *= n--;
            r /= d;
        }
        return r;
    }
    public static int[][] GetCombinations(int[] elements, int length)
    {
        _resultsIndex = 0;
        int numResults = GetBinCoeff(elements.Length, length);
        // observe that here I fully allocate the results array[][]:
        _results = new int[numResults][];
        for (int i = 0; i < numResults; i++)
            _results[i] = new int[length];
        Combinations(elements, length, 0, new int[length]);
        return _results;
    }
    private static void Combinations(int[] input, int len, int startPosition, int[] result)
    {
        if (len == 0)
        {
            Array.Copy(result, _results[_resultsIndex++], result.Length);
            return;
        }
        for (int i = startPosition; i <= input.Length - len; i++)
        {
            result[result.Length - len] = input[i];
            Combinations(input, len - 1, i + 1, result);
        }
    }
}

上面的代码可以这样调用：

[Test]
public void CombinationsUsingArraysOnly()
{
    int[] items = {1, 2, 3};
    var results = CombinationArray.GetCombinations(items, 2);
    for (int i = 0; i < results.GetLength(0); i++)
    {
        string output = "";
        for (int j = 0; j < results[i].Length; j++)
            output += results[i][j] + ",";
        Console.WriteLine(output);
    }
}

结果输出如下：

1,2,
1,3,
2,3,

我尝试了以下方法，但没有成功：

private static IEnumerable<int[]> Combinations(int[] input, int len, int startPosition, int[] result)
{
    if (len == 0)
    {
        yield return result;
    }
    for (int i = startPosition; i <= input.Length - len; i++)
    {
        result[result.Length - len] = input[i];
        Combinations(input, len - 1, i + 1, result);
    }
}

...但是当我 'foreach' return 'IEnumerable<>' 时，它的行为就像计数==0 一样，我没有得到任何结果。我尝试了其他处理产量的方法，但其中 none 结果 "yield" 结果（双关语不好）。

Answer 1

您还需要迭代递归调用。在您的代码中，您只有 return 基本情况，而其余的执行没有 return 任何东西。

private static IEnumerable<int[]> Combinations(int[] input, int len, int startPosition, int[] result)
{
    if (len == 0)
    {
        yield return result;
    }
    else
    {
        for (int i = startPosition; i <= input.Length - len; i++)
        {
            result[result.Length - len] = input[i];

            //// You need to return the results of your recursive call
            foreach (var combination in Combinations(input, len - 1, i + 1, result))
            {
                yield return combination;
            }
        }
    }
}

C# 如何在递归调用期间使用 yield 运算符？

C# how to use yield operator during recursive call?

c#

recursion

yield