Ограниченная производительность с использованием перестановки и рекурсии

Question

Я пишу программу, которая вычисляет самую длинную полосу, взвешенную по их вероятности, и использует рекурсию для получения всех возможных сценариев. Это проблема кодирования, которую я выполняю: https://open.kattis.com/problems/winningstreak

Я заметил, что функция перестановки, которая у меня есть, не самая эффективная, когда дело доходит до большего ввода из-за рекурсии. Пример ввода будет 3, и он добавит следующее в массив совпадений: 000, 010, 001, 011, 100,110,101,111

public static void Permutations(string text, int numberOfGames,     List<String> matches)
    {
        if (numberOfGames > 0)
            for (int j = 0; j < 2; j++)
                Permutations(text + j.ToString(), numberOfGames - 1, matches);
        else
        {
            matches.Add(text.ToString());
        }

    }

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

Спасибо вам, ребята!

Answer 1

Моя проблема заключается в больших входах (пример 500)

Ваша программа пытается создать список из 2⁵⁰⁰ строк.

Во Вселенной примерно 2²⁶⁷ атомов.

Я нахожу неудивительным, что у вас заканчивается память.

Найдите более умное решение вашей проблемы.

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

Также помните, что формулировка проблемы заключается в том, что результат должен быть в пределах некоторой доли от точного результата. Это не должен быть точный результат. Используйте мета-рассуждения, когда имеете дело с такими загадками: человек, который поставил загадку, скорее всего, не смог бы решить эту проблему, если бы это не было чем-то, чем вы могли бы воспользоваться.

Это дает вам некоторое представление о том, как решить проблему?

Если вы хотите больше советов и понимания, начните с чтения этого:

http://gato-docs.its.txstate.edu/mathworks/DistributionOfLongestRun.pdf