Каждая перестановка алфавита до 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 лет.

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