生成排列时出现System.OutOfMemoryException
我在尝试生成6个字母的排列时收到System.OutOfMemoryException 。 5个字母的排列仍然有效。
这是我用来生成所有排列的代码：
private static List getPermutations(int n,string source) { IEnumerable q = source.Select(x => x.ToString()); for (int i = 0; i source, (x, y) => x + y); } return q.ToList(); // THIS IS WHERE THE ERROR HAPPENS }
之后我使用这段代码根据正则表达式过滤它们：
private static List filterListByRegex(List list, string regex) { List 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; }
因为我并不真的需要所有那些排列，有没有办法在生成排列时进行正则表达式过滤，或者我应该使用更有效的代码来生成排列？
这是一张图片，以更好地展示我正在努力实现的目标： 
垂直字母表字符串是我告诉代码使用的字符串。
首先，我想提一下，我们在这里讨论的不是真正的排列，而是所谓的n-tuples或permutations with repetition – 维基百科 。
其次，关于System.OutOfMemoryException when generating permutations ，我认为我们都同意结果不应该存储在列表中，而是以可枚举的forms提供，这将允许应用过滤和消费（最终存储）只有感兴趣的那些。
在这方面，@ juharr提供的LINQ解决方案表现非常出色。 因此，我的目标是最小化中间内存分配，包括字符串连接，并最终得到更通用，更快速的解决方案。
为了做到这一点，我需要做出一些艰难的设计决定。 我正在谈论的一般function的签名将如下所示
public static IEnumerable RepeatingPermutations(this T[] set, int N)
问题是arrays产生的应该是什么。 如果我们遵循recomendations，它们应该是一个单独的数组实例。 但是，请记住我想最小化分配，我决定打破这些规则并产生同一个数组实例，转移不修改它的责任，并在必要时将其克隆到调用者。 例如，这允许调用者不执行成本过滤。 或者像这样在它上面实现OPfunction
public static IEnumerable 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 }
有趣的是，我最近回答了一个与组合相关的问题，并意识到算法几乎是一样的。
尽管如此，这里的function是：
public static IEnumerable RepeatingPermutations(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 []
我们可以看到，内存方面两个字符串函数都是可比的。 性能方面，LINQfunction只慢了约2倍，这是非常好的结果。
正如在这种情况下所预期的那样，非分配function明显优于它们。
更新：根据注释中的要求，以下是上述函数的示例用法（请注意它们是扩展方法，必须放在您选择的静态类中）：
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 Clone(this IEnumerable source) { return source.Select(item => (T[])item.Clone()); }
所以消费电话很简单
var charPermutationList = charSet.RepeatingPermutations(3).Clone().ToList();
这里最好的做法是使用延迟初始化来避免同时在内存中进行所有排列。
private static IEnumerable getPermutations(int n,string source) { IEnumerable 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; } private static List filterListByRegex(IEnumerable list, string regex) { List newList = new List(); foreach(var item in list) { Match match = Regex.Match(item, regex, RegexOptions.IgnoreCase); if (match.Success) { newList.Add(item); } } return newList; }
这可能不是最有效的方法，但至少它应该让你超越内存问题。
这是一个简单的解决方案，既有计算效率，又有内存效率。
- 使用迭代器不是生成整个排列列表然后查找匹配，而是让我们在生成时处理潜在的排列匹配。
- 通过一点回溯，只有有机会匹配你的正则表达式的排列才会生成。
你需要的只是一个额外的正则表达式，接受部分候选人。 如果添加了字符，它应该接受可能成为匹配的字符串。 （在Java中使用像hitEnd（）这样的东西会很好。这可以消除对正则表达式的需要。不幸的是，我不认为在.Net中有相同的东西）
在我的例子中，我想找到匹配正则表达式“32145.67”的字符串“123456789”的排列。 我使用（次优）正则表达式“^ 3 $ | ^ 32 $ | ^ 321”来丢弃不以321开头的排列。（当然，这里可以生成“456789”和prepend的排列“123”的结果，但这只是为了说明这个概念。）
此解决方案的效率主要取决于您可以在排列生成的早期丢弃多少无效匹配。
简要说明排列生成的工作原理 。 让我们尝试生成字符串“abc”的所有排列。 很容易看出：
permutations("abc") = {"a" + permutations("bc"), "b" + permutations("ac"), "c" + permutations("ab")}
换句话说，我们获取输入字符串的每个字符，将其附加到累加器并计算输入字符串的所有排列，并删除该字符。 一旦我们到达一个叶子 – 输入字符串的排列 – ，累加器将具有输入字符串的大小。
这可以在递归伪代码中简洁地写成：
permutation(input, acc) if input empty return acc foreach(character in input) left <- remove char from input permutation(left, acc+char)
现在，这不是生成排列的最有效方法。 （参见Heap的算法）但至少它允许我们不仅仅通过查看它们的前缀来探索整个树结构并丢弃排列。
由于“yield return”在递归函数中不能很好地工作，我只是以迭代的方式重写了解决方案（注意：空间复杂度比上面的递归DFS更差）。
public IEnumerable getPermutation(string input, string regexp) { Stack left = new Stack (); Stack acc = new Stack (); left.Push(input); acc.Push(""); // generate all permutations that match regexp while (left.Count > 0) { string c = left.Pop(); string r = acc.Pop(); if(r.Length==input.Length) { yield return r; } else { for(int i=0;i
在一个点上存储所有这些排列，你的内存不足。
假设长度为5个字符，则有7,893,600种不同的排列。
假设长度为6个字符，则有165,765,600种不同的排列。
考虑到字符串中的每个字符值2个字节的内存，您需要1,989,187,200个字节（大约2千兆字节）来存储所有排列。 这不是完全可取的。
那么我们如何解决这个问题呢？
我从未在c＃中编码，但这是一个实际的设计决策：在自身创建排列时执行单独的处理。 这样，您只需存储所需的排列。 这是一些伪代码：
List storedPermutations; string s = createPermutation(); bool shouldAdd = shouldAddPermutation(s); if (bool) { storedPermutations.add(s); }
这可能不是最好的（也不是伪代码），但这里的逻辑是决定是否在创建时将列表添加到列表中，而不是将所有内容添加到列表中，然后尝试处理整个清单。 如果你的内存不足，那么仍有很多排列。