Перестановка символов C # с повторением на большом наборе символов

Question

Здравствуйте, я пытаюсь получить все возможные комбинации с повторениями данного массива символов.Массив Char состоит из букв алфавита (только ниже), и мне нужно генерировать строки длиной 30 и более символов.

Я пытался использовать метод многих циклов for, но при попытке получить все комбинации символов charв массиве char с длиной строки более 5 я получаю исключение Memory Exception.

Поэтому я создал аналогичный метод, который принимает только первые 200000 строк, затем следующие 2000000 и т. д. Это оказалось успешным, но только с меньшей длиной.strings.

Это был мой метод с длиной 7 символов:

public static int Progress = 0;
public static ArrayList CreateRngUrl7()
        {

            ArrayList AllCombos = new ArrayList();
            int passed = 0;
            int Too = Progress + 200000;

            char[] alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToLower().ToCharArray();

            for (int i = 0; i < alpha.Length; i++)
                for (int i1 = 0; i1 < alpha.Length; i1++)
                    for (int i2 = 0; i2 < alpha.Length; i2++)
                        for (int i3 = 0; i3 < alpha.Length; i3++)
                            for (int i4 = 0; i4 < alpha.Length; i4++)
                                for (int i5 = 0; i5 < alpha.Length; i5++)
                                    for (int i6 = 0; i6 < alpha.Length; i6++)
                                {
                                    if (passed > (Too - 200000) && passed < Too)
                                    {
                                        string word = new string(new char[] { alpha[i], alpha[i1], alpha[i2], alpha[i3], alpha[i4], alpha[i5],alpha[i6] });
                                        AllCombos.Add(word);
                                    }

                                    passed++;
                                }
            if (Too >= passed)
            {
                MessageBox.Show("All combinations of RNG7 were returned");
            }
            Progress = Too;
            return AllCombos;
        }

Я попытался добавить 30 циклов for, как описано выше, чтобы я мог получить строки с длиной 30, но применениепросто зависает. Есть ли лучший способ сделать это?Все ответы будут высоко оценены.Заранее спасибо!

Может кто-нибудь, пожалуйста, просто опубликуйте метод, как это делается с большими строками, я просто хочу увидеть пример?Мне не нужно хранить эти данные, мне просто нужно сравнить их с чем-то и освободить из памяти.Я использовал алфавит, например, мне не нужен весь алфавит. Вопрос был не в том, сколько времени это займет или сколько комбинаций это будет !!!!!

Answer 1

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

Если вы просто хотите проверить строку на наличие условия, вы должны поместить проверку в цикл:

for ( ... some crazy loop ...) {
  var word = ... create word ...
  if (!WordPassesTest(word)) {
    Console.WriteLine(word + " failed test.");
    return false;
  }
}
return true;

Тогда вам нужно только хранилище для одного слова. Конечно, если цикл достаточно сумасшедший, он не прекратится до конца вселенной, как мы ее знаем.

Если вам нужно выполнить много вложенных, но похожих циклов, вы можете использовать рекурсию для упрощения кода. Вот пример, который не является невероятно эффективным, но, по крайней мере, он прост:

Char[] chars = "ABCD".ToCharArray(); 

IEnumerable<String> GenerateStrings(Int32 length) {
  if (length == 0) {
    yield return String.Empty;
    yield break;
  }
  var strings = chars.SelectMany(c => GenerateStrings(length - 1), (c, s) => c + s);
  foreach (var str in strings)
    yield return str;
}

Вызов GenerateStrings(3) сгенерирует все строки длины 3, используя ленивый анализ (поэтому для строк не требуется дополнительная память).

Основываясь на IEnumerable, генерирующем ваши строки, вы можете создавать примитивы для буферизации и обработки буферов строк. Простым решением является использование Reactive Extensions для .NET. Здесь у вас уже есть примитив Buffer:

  GenerateStrings(3)
    .ToObservable()
    .Buffer(10)
    .Subscribe(list => ... ship the list to another computer and process it ...);

Лямбда в Subscribe будет вызываться с List<String>, содержащим не более 10 строк (параметр, указанный в вызове Buffer).

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

Из комментариев к этому вопросу должно быть очевидно, что вы не сможете обработать 26 ^ 30 строк, даже если в вашем распоряжении несколько компьютеров.

Answer 2

Сейчас у меня нет времени на написание кода, но, по сути, если у вас заканчивается ОЗУ, используйте диск. Я думаю, что один поток запускает алгоритм для поиска комбинаций, а другой сохраняет результаты на диск и освобождает оперативную память.