Действительно большой список перестановок

Мой вопрос не зависит от конкретного языка. У меня возникают проблемы с получением цикла для обработки перестановок. Я пытаюсь закодировать что-то, чтобы отобразить все значения для 26^x, где x - длина строки. Нет входной строки не будет поступать так, если x=1, он будет отображать через г, если x=2 Итл дисплей аа через ZZ. az рассматривается как отличный от za.Действительно большой список перестановок

Более конкретно, я хочу запустить это для более длинных строк, более 100 символов в длину, чтобы увидеть, сколько строк заданной длины содержит слова, а не случайные буквы.

источник

2012-04-13 Rickie Marsh

Сложность времени и количество слов n !, для 100 символов - 9 * 10^157. Любой алгоритм займет ДЛИННОЕ время, чтобы сделать слова намного менее обработанными. –

(Из того, что я понимаю). Вы можете рассчитать количество слов для длины, которую произведет ваша программа. Используйте библиотеку словарей для подсчета количества слов заданной длины. Теперь вы можете увидеть количество слов со случайным письмом. –

@JesusRamos Вы можете бросить монету 1000001 раз и имитировать ее займет 2^1000001 шагов, но почти нет времени, чтобы предсказать, победит или уйдет «Голова»! – ElKamina

В комментарии к вопросу, несколько нецелесообразно пытаться перечислить все возможные 100-символьные строки.

Я бы предложил альтернативную стратегию генерации случайных строк заданной длины, а не перечисление структурированным образом. Что-то вроде:

count = 0 
for i from 0 to simulation_length: 
    random_string = '' 
    for j from 0 to string_length: 
     random_string += random_char() 
    // containsWord(string) checks if the random string contains a word 
    // this is tricky in and of itself 
    if (containsWord(random_string)) count++ 
...

случайная выборка даст вам представление о поведении через все пространство, пока simulation_length достаточно.

источник

2012-04-13 05:15:53 mfrankli

Вы могли бы сделать это гораздо более непосредственно, взяв общее количество слов для каждой длины 'n' и деления на' n! ', которая будет частью буквенных строк длиной' n', которые являются словами. Я думаю, что OP спрашивает о том, что слова содержат как подмножество, но это сложнее. – Dougal

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

26^х, где х длина строки ... Я хотел, чтобы запустить это для длинных строк, более 100 символов в длину

Вы должны забыть об этом.

Давайте поместим вещи в перспективе. Есть 26 букв английского алфавита, так общее количество строк с 100 символов в них ...

3142930641582938830174357788501626427282669988762475256374173175398995908420104023465432599069702289330964075081611719197835869803511992549376

Это десятичное число. При скорости 1 строки за миллисекунду для их распечатки потребуется 9,9 * 10^130 лет. Это 7.3 * 10^120 раз дольше, чем вселенная существовала.

Получить список слов или загрузить словарь в память и использовать его вместо этого.

источник

2012-04-13 05:17:51 SigTerm

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

Приятный объем поиска/обработки можно устранить, установив несколько простых правил для первых двух символов. Если q является первым, второе может быть только гласным. То же самое относится и к некоторым другим буквам. 26^2 возможных двухбуквенных комбо, q, например, имеет только 5 действительных комбинаций, где это первая буква. Хотя по-прежнему не будет весело устанавливать множество правил, он устраняет довольно много проблемы. Кроме того, поскольку я рассматриваю строки с определенным словом в определенном месте, он может быть разбит на две части до и после слова. –

Что мы хотели бы видеть, это: Сколько строк размером 50, 51, 52, ... можно построить из словаря со следующими словами: «2: 183, 3: 815, 4: 3181, 5: 6151, 6: 9317, 7: 11962, 8: 11979, 9: 10400, 10: 8065, ... "? Возьмите свои значения из 'for n в {2..20}; do echo -ne "$ n \ t"; egrep -v ". * 's"/usr/share/dict/american-english | egrep -c "^. {" $ n "} $"; done' –

Это будет зависеть от вашего определения «слова». Если «a» - это слово, очень легко получить нижний предел вероятности получения слова в последовательности из 100 символов (примерно 1/e^4). Точно так же вы можете рассмотреть 2 буквенных слова и 3 буквенных слова и уточнить вероятность. После 4 или 5 букв эта вероятность становится действительно точной, потому что есть несколько более длинных слов, и они случайным образом встречаются очень редко.

источник

2012-04-13 06:42:25 ElKamina

Он должен дать более одного слова в заданной длины строки. Если пользователь ставит 8, он может вернуть «itisadog» или «wesaidno». Глядя на это так, наличие словаря и поиск всех слов для добавления до данной длины кажется лучше –

@ RickieMarsh: Но вы не ожидаете, что они будут иметь смысл? Значит, 'nosaidwe' и' nonoweno' будут соответствовать? –

Действительно большой список перестановок

ответ

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