Исключение System.OutOfMemoryException при генерации перестановок

Я получаю 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;
        }

так как на самом деле мне не нужны ВСЕ эти перестановки, есть ли способ регулярного фильтра при генерации перестановок, или я должен использовать более эффективный фрагмент кода для генерации перестановок?

Вот изображение, чтобы лучше продемонстрировать то, что я пытаюсь достичь:

Строка вертикального алфавита - это тот, который я говорю используемому коду.

Ответ 1

Во-первых, я хотел бы упомянуть, что мы обсуждаем здесь не настоящие перестановки, а так называемые n-tuples или permutations with repetition - Wikipedia.

Во-вторых, в отношении System.OutOfMemoryException when generating permutations, я думаю, мы все согласны с тем, что результат не должен быть сохранен в списке, но представлен как перечислимый, который позволит применять фильтрацию и потребление (в конечном счете, хранение) только те, которые интересны.

В этом отношении решение LINQ, предоставленное @juharr, работает очень хорошо. Поэтому мои цели сводятся к минимуму распределения промежуточной памяти, включая конкатенации строк, а также в конечном итоге с более общим и быстрым решением.

Чтобы сделать это, мне нужно принять какое-то твердое решение. Подпись общей функции, о которой я говорю, будет выглядеть следующим образом:

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 }

Интересно, что недавно я ответил на комбинации question и понял, что алгоритмы практически одинаковы.

При всем том, что сказано, вот функция:

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

Ответ 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;
}

Это может быть не самый эффективный способ сделать это, но, по крайней мере, это должно помочь вам решить проблемы с памятью.

Ответ 3

Вот простое решение, которое эффективно и эффективно для памяти.

Вместо того, чтобы генерировать весь список перестановок и затем находить совпадения, использование итератора позволяет нам обрабатывать возможные совпадения перестановок по мере их создания.
С небольшим отступлением можно создать только перестановки, которые имеют возможность соответствовать вашему регулярному выражению.

Все, что вам нужно, - это дополнительное регулярное выражение, которое принимает частичных кандидатов. Он должен принимать строки, которые могут стать совпадением, если персонажи будут добавлены. (Было бы неплохо иметь что-то вроде hitEnd() в Java, которое делает именно это. Это устранит необходимость в этом регулярном выражении. К сожалению, я не думаю, что есть эквивалент в .Net)

В моем примере я хочу найти перестановки строки "123456789", которые соответствуют регулярному выражению "32145.67". Я использую (субоптимальное) регулярное выражение "^ 3 $| ^ 32 $| ^ 321", чтобы отменить перестановки, которые не начинаются с 321. (Конечно, здесь было бы возможно сгенерировать перестановки для "456789" и добавить "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)

Теперь это не самый эффективный способ генерации перестановок. (см. алгоритм кучи). Но по крайней мере это позволяет нам не исследовать всю древовидную структуру и отказаться от перестановок, просто взглянув на их префикс.

Так как "yield return" не так хорошо работает в рекурсивных функциях, я просто перезаписал решение итеративным образом (примечание: сложность пространства хуже, чем при вышеупомянутой рекурсивной DFS).

public IEnumerable<string> getPermutation(string input, string regexp)
{
        Stack<string> left = new Stack<string>();
        Stack<string> acc = new Stack<string>();

        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<c.Length;i++)
                {
                    string p = r + c[i];
                    if (Regex.IsMatch(p,regexp)) // continue if we have a potential match
                    {
                        left.Push(c.Substring(0, i) + c.Substring(i + 1));
                        acc.Push(p);
                    }
                }
            }

        }            
}



foreach(var a in getPermutation("123456789", "^3$|^32$|^321"))
{
    if(Regex.IsMatch(a, "32145.67"))
    {
         // found match
    }

}

Ответ 4

У вас заканчивается память, сохраняя все эти перестановки в одной точке.

Предполагая длину 5 символов, существует 7 893 600 различных перестановок.
Предполагая длину 6 символов, существует 165,765,600 различных перестановок.

Учитывая, что каждый символ в строке стоит 2 байта памяти, вам понадобится 1,989,187,200 байт (всего около 2 гигабайт) для хранения всех перестановок. Это не совсем желательно.

Итак, как мы это исправим?

Я никогда не кодировал в С#, но здесь практическое дизайнерское решение: выполнять индивидуальную обработку, когда сама перестановка создается. Таким образом, вам нужно только сохранить необходимые вам перестановки. Вот несколько псевдокодов:

List<string> storedPermutations;
string s = createPermutation();
bool shouldAdd = shouldAddPermutation(s);
if (bool) 
{
    storedPermutations.add(s);
}

Это, возможно, не самый лучший (и это, вероятно, псевдокод), но логика здесь заключается в том, чтобы решить, добавить ли перестановку в список момента его создания, вместо того, чтобы добавлять все в список, а затем пытаться для обработки всего списка. Если у вас все еще не хватает памяти, тогда еще много перестановок.