生成排列时System.OutOfMemoryException

Question

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

因为我并不真的需要所有那些排列,有没有办法在生成排列时使用正则表达式过滤器,或者我应该使用更高效的代码片段来生成排列？

这是一张图片,以更好地展示我正在努力实现的目标:

垂直字母表字符串是我告诉代码使用的字符串.

Answer 1

首先,我想提一提,我们在此讨论的是不是真实的排列,但所谓的n-tuples还是permutations with repetition- 维基百科.

其次,关于System.OutOfMemoryException when generating permutations,我认为我们都同意结果不应该存储在列表中,而是作为可枚举提供,这将允许应用过滤和消费(最终存储)仅感兴趣的那些.

在这方面,@ juharr提供的LINQ解决方案表现非常出色.因此,我的目标是最小化中间内存分配,包括字符串连接,并最终得到更通用,更快速的解决方案.

为了做到这一点,我需要做出一些艰难的设计决定.我正在谈论的一般功能的签名将如下所示

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

问题是阵列产生的应该是什么.如果我们遵循recomendations,它们应该是一个单独的数组实例.但是,请记住我想最小化分配,我决定打破这些规则并产生同一个数组实例,转移不修改它的责任,并在必要时将其克隆到调用者.例如,这允许调用者不执行成本过滤.或者像这样在它上面实现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 - LINQ函数来自@juharr
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();

Answer 2

这里最好的做法是使用延迟初始化来避免同时在内存中进行所有排列.

private static IEnumerable<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; 
}

private static List<string> filterListByRegex(IEnumerable<string> list, string regex)
{
    List<string> newList = new List();
    foreach(var item in list)
    {
        Match match = Regex.Match(item, regex, RegexOptions.IgnoreCase);
        if (match.Success)
        {
            newList.Add(item);
        }
    }

    return newList;
}

这可能不是最有效的方法,但至少应该让你超越内存问题.