Перестановки английского алфавита заданной длины

У меня есть этот код. Не уверен, что это работает, потому что время выполнения программы все еще продолжается.Перестановки английского алфавита заданной длины

void permute(std::vector<std::string>& wordsVector, std::string prefix, int  length, std::string alphabet) { 
if (length == 0) { 
    //end the recursion 
    wordsVector.push_back(prefix); 
} 
else { 
    for (int i = 0; i < alphabet.length(); ++i) { 
     permute(wordsVector, prefix + alphabet.at(i), length - 1, alphabet); 
    } 
}}

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

Алфавит состоит из A-Z в строке длиной 26. WordsVectors содержит все различные комбинации слов. префикс должен проходить через рекурсивно до тех пор, пока не будет сделано слово, а длина будет самоочевидной.

Пример, если я даю длину 7 функции, я ожидаю размер 26 x 25 x 24 x 23 x 22 x 21 x 20 = 3315312000, если я прав, следуя формуле для перестановок. Я не думаю, что программы предназначены для запуска так долго, чтобы либо я попадал в бесконечный цикл, либо что-то не так с моим подходом. Пожалуйста, порекомендуйте. Благодарю.

источник

2015-03-13 Kthieu

Я бы не использовал рекурсии на этом. Учитывая количество вызовов функций, я удивлен, что вы не попали в переполнение стека. – NathanOliver

программа займет много времени, поскольку сложность задается выбором n (n <= 26) вещей из 26, а затем ее перестановкой. Он будет очень быстрым для n, и, следовательно, сложность высока. Его не бесконечный цикл просто займет невероятно длинный – sashas

У вас достаточно памяти для хранения слов? –

Конечно стек переполнится, но сосредоточившись на своем вопросе, даже если вы пишете итеративный программу займет много времени (а не бесконечный цикл просто очень долго)

[26L, 650L, 15600L, 358800L, 7893600L, 165765600L, 3315312000L, 62990928000L, 1133836704000L, 19275223968000L, 308403583488000L, 4626053752320000L, 64764752532480000L, 841941782922240000L, 10103301395066880000L, 111136315345735680000L, 1111363153457356800000L, 10002268381116211200000L, 80018147048929689600000L, 560127029342507827200000L, 3360762176055046963200000L, 16803810880275234816000000L, 67215243521100939264000000L, 201645730563302817792000000L, 403291461126605635584000000L, 403291461126605635584000000L]

приведенный выше список является числом возможности для 1<=n<=26. Вы можете видеть, как n увеличивает количество возможностей. Скажем, у вас 1 ГГц процессор, который выполняет 10^9 операций в секунду. Скажем, рассмотрим количество возможностей для n=26 его 403291461126605635584000000L. Очевидно, что если вы присядете, чтобы перечислять все возможности так долго (так много лет), что вы почувствуете, что он достиг бесконечного цикла. Наконец, я не очень внимательно смотрел на ваш код, но в двух словах, даже если вы его правильно пишете, итеративно и не сохраняете (опять-таки не может иметь столько памяти), и просто распечатывайте все возможности, и это займет много времени для больших значениями n.

EDIT

Как jaromax и другие сказали, что если вы просто хотите, чтобы написать это для меньших значений n, говорят меньше, чем 10-12 вы можете написать итеративный программу для вывода списка/распечатать их. Он будет работать довольно быстро для небольших значений. Но если вы также захотите их сохранить, то n должен сказать меньше 5. (Действительно, зависит от того, сколько оперативной памяти доступно, или вы можете найти некоторые перестановки, записывая их на диск, а затем зависит от того, сколько дисковой памяти вы можете сэкономить, снова ссылайтесь на количество списков возможностей, которые я разместил выше. Это дает приблизительное представление о времени и пространственная сложность).

источник

2015-03-13 12:53:27 sashas

Хорошо, я понимаю, что вы имеете в виду. Что если вместо хранения я использую эти слова для поиска слов в словаре, хранящемся в двоичном дереве поиска? – Kthieu

, тогда сложность памяти была бы прекрасной, но временная сложность все равно была бы плохой, поскольку я сказал, что даже распечатывать все возможности по очереди требуется время. Поэтому любое вычисление по всем возможностям один за другим неизбежно займет много времени. – sashas

Я думаю, что может возникнуть проблема, когда вы делаете это в стеке. Большая часть вычисления выполняется рекурсивно, а это означает, что каждый раз выделяется пространство для функции.

Попробуйте переформулировать его линейно. Кажется, у меня была такая проблема раньше.

источник

2015-03-13 12:40:10 jaromrax

Это не дает ответа на вопрос. Чтобы критиковать или запросить разъяснения у автора, оставьте комментарий ниже своего сообщения - вы всегда можете прокомментировать свои собственные сообщения, и как только у вас будет достаточно [репутации] (http://stackoverflow.com/help/whats-reputation), вы будете быть в состоянии [прокомментировать любое сообщение] (http://stackoverflow.com/help/privileges/comment). – Malvineous

Спасибо. Вы правы, что мне нужна репутация, чтобы комментировать. Тем не менее, я все еще думаю, что я ** дал ответ ** .... Предположим, что @Kthieu сделал свое исчисление правильным, и у него есть 3315312000 комбинаций, (7 букв я получаю 3e + 8 комбинаций), вам нужно 2 ГБ для хранения и Я просто проверил plain C, и я могу делать операции на 20 миллинов, такие как r = r * n/(n + 1) + r/n; 'в секунду. Мое резюме - не проблема, если делать это в куче. – jaromrax

Ваш вопрос предполагает, что вы думаете, есть 26x25x24x ... Перестановки

Ваш код не имеет ничего я могу видеть, чтобы избежать «ааааааа» быть перестановка, в этом случае имеется 26x26x26x ...

Так что, помимо очень сложного способа подсчета в базе 26, я думаю, что это также дает плохие ответы?

источник

2015-03-13 13:21:27

Я вижу это сейчас. Я всегда начинаю с первой буквы алфавита. но такие комбинации, как ABAAAAA, также существуют? – Kthieu

Если вы делали числа, вы получили бы 0001, 0002, 0003, 0004 .... что вы используете буквы вместо этого, это не очень важно, вы в основном считаете в базе 26 и сохраняете каждое значение в виде строки ... Я пытался сказать, что это странно, и это странный способ сделать это? –

Перестановки английского алфавита заданной длины

ответ

Смежные вопросы