生成排列时出现System.OutOfMemoryException

一尘不染

生成排列时出现System.OutOfMemoryException

algorithm

我正在System.OutOfMemoryException尝试生成6个字母排列。5个字母排列仍然有效。

这是我用来生成所有排列的代码：

private static List<string> getPermutations(int n,string source)
        {
            IEnumerable<string> q = source.Select(x => x.ToString());
            for (int i = 0; i < n - 1; i++)
            {
                q = q.SelectMany(x => source, (x, y) => x + y);
            }
            return q.ToList(); // THIS IS WHERE THE ERROR HAPPENS
        }

之后，我将使用这段代码根据正则表达式对它们进行过滤：

private static List<string> filterListByRegex(List<string> list, string regex)
        {
            List<string> newList = list.ToList();
            for (int i = newList.Count - 1; i >= 0; i--)
            {
                Match match = Regex.Match(""+newList[i], regex, RegexOptions.IgnoreCase);
                if (!match.Success)
                {
                    newList.RemoveAt(i);
                }
            }
            return newList;
        }

因此，由于我实际上并不需要所有这些排列，因此在生成排列时是否可以使用正则表达式过滤器，还是应该使用更高效的代码来生成排列？

这是一张图片，可以更好地演示我要实现的目标：

垂直字母字符串是我要告诉代码使用的字符串。

阅读 227

2020-07-28

共1个答案

一尘不染

首先，我想提一提，我们在此讨论的是不是真实的排列，但所谓的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 set
from e2 in set
...
from eN in set
select 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=     29K
B1: N=2 Count=         676 Time=00:00:00.0000263 Memory=     16K
B2: N=2 Count=         676 Time=00:00:00.0000189 Memory=      8K

A : N=3 Count=      17,576 Time=00:00:00.0010107 Memory=    657K
B1: N=3 Count=      17,576 Time=00:00:00.0003673 Memory=    344K
B2: N=3 Count=      17,576 Time=00:00:00.0001415 Memory=      8K

A : N=4 Count=     456,976 Time=00:00:00.0184445 Memory=  2,472K
B1: N=4 Count=     456,976 Time=00:00:00.0096189 Memory=  2,520K
B2: N=4 Count=     456,976 Time=00:00:00.0033624 Memory=      8K

A : N=5 Count=  11,881,376 Time=00:00:00.4281349 Memory=    397K
B1: N=5 Count=  11,881,376 Time=00:00:00.2482835 Memory=  4,042K
B2: N=5 Count=  11,881,376 Time=00:00:00.0887759 Memory=      8K

A : N=6 Count= 308,915,776 Time=00:00:11.2697326 Memory=  1,688K
B1: N=6 Count= 308,915,776 Time=00:00:06.5638404 Memory=  1,024K
B2: 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();

2020-07-28