Каждая перестановка алфавита до 29 символов?

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

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

Ответы на решения в PHP, Processing , C ++ или Java (я знаком с ними, PHP предпочтителен, но, вероятно, нет лучшего для этого, я должен представить).

Или даже просто псевдокод / ​​идеи будут оценены.

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

Solutions Collecting From Web of "Каждая перестановка алфавита до 29 символов?"

Слово «перестановка» обычно означает, что каждая буква появляется ровно один раз, поэтому невозможно было бы создать любую перестановку с более чем 26 буквами. Во всяком случае, поскольку число сгенерированных строк слишком велико, вместо этого вы можете использовать случайные строки (следующий код C):

char s[30]; int p; for (;;) // repeat forever: you cannot use a realistic iteration limit anyway { for (p = 0; p < 29; ++p) s[p] = 'a' + rand() % 26; s[29] = '\0'; puts(s); } 
 void out_perms(std::string word) { std::vector<int> indexes(word.size()); for (size_t i = 0; i < indexes.size(); ++i) indexes[i] = i; do { for (size_t i = 0; i < indexes.size(); ++i) std::cout << word[indexes[i]]; std::cout << std::endl; } while (std::next_permutation(indexes.begin(), indexes.end())); } int main(int, char**) { out_perms("asdfg"); } 

См. http://codepad.org/6lQTPQrG, например, вывод

Очевидно, внешний цикл for – количество символов в вашем слове. Затем вы просто создаете строки с такой длиной. Для длины 5 вы начинаете с «AAAAA», затем «AAAAB», «AAAAC».

Как только вы нажмете «Z», вы вернетесь и переместите персонаж слева вверху, т.е. «AAAAZ» станет «AAABA», а «AAAZZ» станет «AABAA». Как только вы нажмете «ZZZZZ», вы закончите с внутренним циклом, а внешний цикл начнется с «AAAAAA».

Вот простая непроверенная программа на C ++, которая создает слова путем подсчета в Base 26:

 #include <string> #include <iostream> int main(void) { //---------------------------------------------------------- // Print permuations of strings of letters up to length 5. // Use base 26 arithmetic. //---------------------------------------------------------- const unsigned int MAX_ITERATIONS = 26 * 26 * 26 * 26 * 26; std::string word = "A"; for (unsigned int i = 0; i < MAX_ITERATIONS; ++i) { //------------------------------------------------------ // Print the word //------------------------------------------------------ std::cout << word << std::endl; //------------------------------------------------------ // Increment the word, using base 26 arithmetic. // A, B, C, ..., Z. // AA, BA, CA, ..., ZA, AB, BB, CB, DB, ..., ZZ. // AAA, BAA, CAA, ..., ZAA, ABA, BBA, CBA, DBA, ..., ZZZ. //------------------------------------------------------ bool carry_generated = false; unsigned int digit = 0; do { carry_generated = false; if (word[digit] < 'Z') { ++word[digit]; break; } word[digit++] = 'A'; if (word.length() == digit) { word += "A"; break; } carry_generated = true; } while (carry_generated && (digit < 5)); } return 0; } 

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

Это самая большая проблема со словом длиной 29. Количество переполняет диапазон стандартных целых чисел без знака C ++. Библиотека Big Int должна быть использована. Следующий вопрос – время, необходимое для обработки каждой комбинации. Умножьте количество на 1 микросекунду на итерацию (в худшем случае) и уменьшите до суток, часов, минут и секунд. Возможно, потребуются годы.

Использование прироста символов в стиле Perl в PHP.

 set_time_limit(0); $perm = 'A'; $endTest = str_repeat('Z',28).'A'; while ($perm != $endTest) { echo $perm++,"\n"; } 

Запустите сценарий из командной строки, чтобы вы не ударили тайм-аут веб-сервера; затем откиньтесь и подождите несколько лет, чтобы завершить

 function p($length, $partial) { if ($length == 0) return $partial; $ans = array(); foreach (range('a', 'z') as $i) { $ans[] = p($length -1, $partial . $i); } return $ans; } $top = 3; //$f = fopen('out.txt'); for ($l = 1; $l < $top+1; $l++) { print_r(p($l), ''); //fwrite($p($l), ''); } 

Если вы хотите установить $top до 29 и попробовать попробовать. Я не собираюсь.

EDIT – print_r(p($l), ''); —> print_r(p($l, ''));

PHP продолжает впечатлять меня своей терпимостью к ошибкам. Отсутствует «обязательный» аргумент для моего p ? без проблем itll просто будет пустой строкой как-то (или нулевой, или ложной, в зависимости от ситуации). Второй аргумент «print_r»? без разницы, обрабатывается как false по умолчанию

РЕДАКТИРОВАТЬ

Я не знаю, какого черта я здесь делал. Различные типы возврата p довольно нечетны и возвращают составной массив со странной структурой.

В любом случае это гораздо лучшее решение

 $lengthDesired = 29; for($i='a'; $i != str_pad('',$lengthDesired+1,'a'); $i++) echo $i .', '; 

Вот генератор перестановок, написанный в java http://www.merriampark.com/perm.htm .

Однако, как он упоминает

  //----------------------------------------------------------- // Constructor. WARNING: Don't make n too large. // Recall that the number of permutations is n! // which can be very large, even when n is as small as 20 -- // 20! = 2,432,902,008,176,640,000 and // 21! is too big to fit into a Java long, which is // why we use BigInteger instead. //---------------------------------------------------------- 

Поскольку ваше n равно 29, вы будете ждать долгое и долгое время. Он слишком велик, поскольку EboMike пытается рассказать вам в своих комментариях.

прямо с головы (PHP).

 $index = 0; while(1) { $output_string = ''; $base_26 = (string)base_convert($index, 10, 26); if (strlen($base_26) > 29) break; for ($i = 0; $i < strlen($base_26); $i++) { $output_string .= chr(65 + base_convert($base_26[$i], 26, 10)); } $index++; echo $output_string; } 

Это то, что я сделал бы:

 #include <iostream> void printWords(std::string& word, int index, int last) { std::cout << word << "\n"; if (index != last) { for(char loop = 'a'; loop <= 'z'; ++loop) { word[index] = loop; printWords(word, index+1, last); } word[index] = ' '; } } int main() { std::string word(" "); // 29 space printWords(word,0,word.length()); } 

Решение Java, которое должно сделать трюк:

 public void characterPermutations(int length, LinkedList<String> permutations) { if(length > 1) { characterPermutations(length - 1, permutations); ListIterator<String> iterator = permutations.listIterator(); while(iterator.hasNext()) { String permutation = iterator.next(); for(char c = 'a'; c <= 'z'; c++) { iterator.add(c + permutation); } } } else { for(char c = 'a'; c <= 'z'; c++) { permutations.add(c + ""); } } } 
 public class hii { public static void main(String[] args){ String[] database = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"}; for(int i=1; i<=database.length; i++){ String[] result = getAllLists(database, i); for(int j=0; j<result.length; j++){ System.out.println(result[j]); } } } public static String[] getAllLists(String[] elements, int lengthOfList) { //initialize our returned list with the number of elements calculated above String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)]; //lists of length 1 are just the original elements if(lengthOfList == 1) return elements; else { //the recursion--get all lists of length 3, length 2, all the way up to 1 String[] allSublists = getAllLists(elements, lengthOfList - 1); //append the sublists to each element int arrayIndex = 0; for(int i = 0; i < elements.length; i++){ for(int j = 0; j < allSublists.length; j++){ //add the newly appended combination to the list allLists[arrayIndex] = elements[i] + allSublists[j]; arrayIndex++; } } return allLists; } } } 

Самый простой способ, я могу думать, чтобы получить каждую перестановку от 1 char до 29 символов в псевдокоде:

 loop from i = 1 to 26^29 or 27^29 if you want to include spaces { convert i to base 26 or 27; translate each number to the corresponding letter; } 

Даже если вы можете сохранить это на диске, как указано в тиридоте, у вас не хватит времени на это.

Просто генерируя (и не сохраняя) все 6-буквенные возможности, занявшие 24 секунды на моем компьютере:

 $ time perl letters.pl real 0m24.837s user 0m24.765s sys 0m0.030s 

Это 7.7X10 ^ -8s за слово. Это означает, что для этого потребуется 8.4×10 ^ 33s или 2.6×10 ^ 26 лет.

Вам нужно больше думать о вашем алгоритме.