如何使用递归收益生成所有替换组合？ C＃

Question

此处的目标是使用递归生成所有与替换的组合，使其不超过 RAM。 yield 运算符就是为此而设计的。我想使用 yield 运算符，因为如果不这样做，我将超出可用 RAM。我组合的元素数量导致有数十亿种组合。

我确定了如何使用递归收益生成所有组合而不用替换。以下是我写的例子：

public static IEnumerable<int[]> GetCombinationsWithYield(this int[] elements, int length)
{
   return Combinations2(elements, length, 0, new int[length]);
}

private static IEnumerable<int[]> Combinations2(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];

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

您可以使用以下单元测试对此进行测试：

[Test]
public void CombinationsUsingArraysOnlyWithYield()
{
    // use this method when RAM consumption is a concern.

    int[] items = {1, 2, 3};

    var results = new int[3][];
    for (int i = 0; i < results.Length; i++)
        results[i] = new int[2];

    int index = 0;

    var stopwatch = new Stopwatch();
    stopwatch.Start();

    // i only copy the results in to an array so that I don't benchmark Console.WriteLine stuff.
    // for this to be truly useful, you would not want to copy the results.
    foreach (var result in items.GetCombinationsWithYield(2))
    {
        Array.Copy(result, results[index], 2);
        index++;
    }

    stopwatch.Stop();

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

    Console.WriteLine("elapsed: " + stopwatch.ElapsedTicks + "[ticks]");
}

输出为：

1,2,
1,3,
2,3,
elapsed: 56597[ticks]

但如您所见，该示例没有替换。

另一方面，我想用这个和替换，这样输出看起来像这样：

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

这是我使用 Linq 解决方案实现的。但它不使用 yield 运算符并溢出我的 RAM。这是解决方案：

public static List<List<T>> GetCombinations<T>(this IEnumerable<T> pool, int comboLength, bool isWithReplacement)
{
    if (isWithReplacement)
        return GetCombinations(pool, comboLength).Select(c => c.ToList()).ToList();

}

private static IEnumerable<IEnumerable<T>> GetCombinations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new[] {t});

    return GetCombinations(list, length - 1).SelectMany(t => list, (t1, t2) => t1.Concat(new[] {t2}));
}

如有任何帮助，我们将不胜感激。熟悉 Knuth 算法的人是理想的选择。

Answer 1

您使用的 LINQ 操作是使用迭代器块在内部实现的。您实质上是在寻求一种将这些操作内联到解决方案中的解决方案。 这将导致与您当前的解决方案完全相同的问题。它会导致您创建吨昂贵的状态机，这些状态机几乎都被丢弃了。为避免占用极高的内存空间，您首先需要避免创建如此多的状态机。编写递归迭代器块不会实现这一点。编写迭代而非递归解决方案（无论是否为迭代器块）将是实现该目标的一种方式。

迭代解决方案非常简单，内存占用量不变。您只需要计算组合的数量，然后为每个组合计算具有该唯一索引的组合（这很简单）。

private static IEnumerable<IEnumerable<T>> GetCombinations<T>(IList<T> list, int length)
{
    var numberOfCombinations = (long)Math.Pow(list.Count, length);
    for(long i = 0; i < numberOfCombinations; i++)
    {
        yield return BuildCombination(list, length, i);
    }
}
private static IEnumerable<T> BuildCombination<T>(
    IList<T> list, 
    int length, 
    long combinationNumber)
{
    var temp = combinationNumber;
    for(int j = 0; j < length; j++)
    {
        yield return list[(int)(temp % list.Count)];
        temp /= list.Count;
    }
}

Answer 2

我认为您已经找到了解决方案。我对您的代码做了一些小修改

public static IEnumerable<List<T>> GetCombinations<T>(IEnumerable<T> pool, int comboLength, 
bool isWithReplacement) // changed this to return an enumerable
{
     foreach (var list in GetCombinations(pool, comboLength).Select(c => c.ToList()))
     {
             yield return list; // added a yield return of the list instead of returning a to list of the results
     }
}

private static IEnumerable<IEnumerable<T>> GetCombinations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new[] { t });

    return GetCombinations(list, length - 1).SelectMany(t => list, (t1, t2) => t1.Concat(new[] { t2 }));
}

我用这个测试过：

    List<int> items = new List<int>();   

    for (int i = 1; i < 100; i++)
    {
        items.Add(i);
    }
    Stopwatch s = new Stopwatch();
    s.Start();
    int count = 0;
    foreach (var list in GetCombinations(items, 4))
    {
        count++;
    }
    s.Stop();
    Console.WriteLine(count);
    Console.WriteLine(s.ElapsedMilliseconds);
    Console.ReadLine();

这运行很好，在 7587 毫秒内没有内存问题，并生成了 96,059,601 种组合。

如何使用递归收益生成所有替换组合？ C＃

How to generate all combinations with replacement using recursive yield? C#

c#

recursion

yield