生成排列时出现System.OutOfMemoryException

生成排列时出现System.OutOfMemoryException

首先，我想提一提，我们在此讨论的是不是真实的排列，但所谓的

n-tuples

还是

permutations with repetition

-
维基百科。

其次，关于

System.OutOfMemoryException when generatingpermutations

，我认为我们都同意结果不应存储在列表中，而应以可枚举的形式提供，这将允许仅对感兴趣的对象进行过滤和使用（最终存储）。

在这方面，@ juharr提供的LINQ解决方案运行良好。因此，我的目标是最大程度地减少中间存储分配，包括字符串连接，并最终获得更通用，更快速的解决方案。

为此，我需要做出一些艰难的设计决定。我正在谈论的通用函数的签名如下所示

public static IEnumerable<T[]> RepeatingPermutations<T>(this T[] set, int N)

问题是应该产生什么数组。如果我们遵循建议，它们应该是一个单独的数组实例。但是，请记住，我想最小化分配，我决定打破该规则并产生一个相同的数组实例，将不修改它的责任移交给调用者，如有必要，请克隆它。例如，这允许呼叫者不执行费用过滤。或者像这样在其上面实现OP功能

public static IEnumerable<string> RepeatingPermutations(this string set, int N){    return set.ToCharArray().RepeatingPermutations(N).Select(p => new string(p));}

关于算法的几句话。与其像其他回答者一样递归地看待这个问题，我想有效地实现类似这样的东西

from e1 in setfrom e2 in set...from eN in setselect new [] { e1, e2, .., eN }

有趣的是，我最近回答了一个与组合有关的问题，并意识到算法几乎相同。

说了这么多，这里是函数：

public static IEnumerable<T[]> RepeatingPermutations<T>(this T[] set, int N){    var result = new T[N];    var indices = new int[N];    for (int pos = 0, index = 0; ;)    {        for (; pos < N; pos++, index = 0)        { indices[pos] = index; result[pos] = set[index];        }        yield return result;        do        { if (pos == 0) yield break; index = indices[--pos] + 1;        }        while (index >= set.Length);    }}

我通过简单地使用N = 2,3，.. 6调用不同的函数并进行迭代和计数来进行了一些测试。这是我的机器上的结果：

A : N=2 Count=         676 Time=00:00:00.0000467 Memory=     29KB1: N=2 Count=         676 Time=00:00:00.0000263 Memory=     16KB2: N=2 Count=         676 Time=00:00:00.0000189 Memory=      8KA : N=3 Count=      17,576 Time=00:00:00.0010107 Memory=    657KB1: N=3 Count=      17,576 Time=00:00:00.0003673 Memory=    344KB2: N=3 Count=      17,576 Time=00:00:00.0001415 Memory=      8KA : N=4 Count=     456,976 Time=00:00:00.0184445 Memory=  2,472KB1: N=4 Count=     456,976 Time=00:00:00.0096189 Memory=  2,520KB2: N=4 Count=     456,976 Time=00:00:00.0033624 Memory=      8KA : N=5 Count=  11,881,376 Time=00:00:00.4281349 Memory=    397KB1: N=5 Count=  11,881,376 Time=00:00:00.2482835 Memory=  4,042KB2: N=5 Count=  11,881,376 Time=00:00:00.0887759 Memory=      8KA : N=6 Count= 308,915,776 Time=00:00:11.2697326 Memory=  1,688KB1: N=6 Count= 308,915,776 Time=00:00:06.5638404 Memory=  1,024KB2: N=6 Count= 308,915,776 Time=00:00:02.2674431 Memory=      8K

哪里

A-@juharr的LINQ函数
B1-我的字符串
B2函数-我的char []函数

如我们所见，在内存方面，两个字符串函数都是可比的。在性能方面，LINQ函数仅慢2倍左右，这是相当不错的结果。

如在这种情况下所预期的那样，非分配功能明显优于它们两者。

更新： 根据注释中的要求，这是上述函数的示例用法（请注意，它们是扩展方法，必须放在您选择的静态类中）：

var charSet = Enumerable.Range('A', 'Z' - 'A' + 1).Select(c => (char)c).ToArray();var charPermutations = charSet.RepeatingPermutations(3);var stringSet = new string(charset);var stringPermutations = stringSet.RepeatingPermutations(3);

但是，请记住我所做的设计选择，因此，如果

charPermutations

在调试器中扩展内部，将看到一个相同的值（最后一个排列）。消耗上述要求的整个结果

char[]

应该是这样的

var charPermutationList = charSet.RepeatingPermutations(3)    .Select(p => (char[])p.Clone()).ToList();

实际上，对以下两种扩展方法的补充是：

public static IEnumerable<T[]> Clone<T>(this IEnumerable<T[]> source){    return source.Select(item => (T[])item.Clone());}

所以消费电话会很简单

var charPermutationList = charSet.RepeatingPermutations(3).Clone().ToList();