Сгенерировать список всех возможных перестановок строки

Следующая recursion Java печатает все перестановки заданной строки:

 //call it as permut("",str); public void permut(String str1,String str2){ if(str2.length() != 0){ char ch = str2.charAt(0); for(int i = 0; i <= str1.length();i++) permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()), str2.substring(1,str2.length())); }else{ System.out.println(str1); } } 

Ниже приведена обновленная версия вышеперечисленного метода «перестановки», которая делает n! (n факториал) менее рекурсивных вызовов по сравнению с указанным выше методом

 //call it as permut("",str); public void permut(String str1,String str2){ if(str2.length() > 1){ char ch = str2.charAt(0); for(int i = 0; i <= str1.length();i++) permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()), str2.substring(1,str2.length())); }else{ char ch = str2.charAt(0); for(int i = 0; i <= str1.length();i++) System.out.println(str1.substring(0,i) + ch + str1.substring(i,str1.length()), str2.substring(1,str2.length())); } } 

Я не уверен, почему вы хотели бы сделать это в первую очередь. Полученный набор для любых умеренно больших значений x и y будет огромным и будет экспоненциально расти, так как x и / или y будут больше.

Допустим, что ваш набор возможных символов – это 26 строчных букв алфавита, и вы попросите свое приложение сгенерировать все перестановки, где длина = 5. Предполагая, что вы не исчерпали память, вы получите 11 881 376 (т.е. 26 на мощность из 5). Увеличьте эту длину до 6, и вы получите 308 915 776 строк назад. Эти цифры очень болезненны, очень быстро.

Вот решение, которое я собрал в Java. Вам нужно предоставить два аргумента времени выполнения (соответствующие x и y). Повеселись.

 public class GeneratePermutations { public static void main(String[] args) { int lower = Integer.parseInt(args[0]); int upper = Integer.parseInt(args[1]); if (upper < lower || upper == 0 || lower == 0) { System.exit(0); } for (int length = lower; length <= upper; length++) { generate(length, ""); } } private static void generate(int length, String partial) { if (length <= 0) { System.out.println(partial); } else { for (char c = 'a'; c <= 'z'; c++) { generate(length - 1, partial + c); } } } } 

 import java.util.*; public class all_subsets { public static void main(String[] args) { String a = "abcd"; for(String s: all_perm(a)) { System.out.println(s); } } public static Set concat(String c, Set lst) { HashSet ret_set = new HashSet(); for(String s: lst) { ret_set.add(c+s); } return ret_set; } public static HashSet all_perm(String a) { HashSet set = new HashSet(); if(a.length() == 1) { set.add(a); } else { for(int i=0; i 

Вот нерекурсивная версия, с которой я столкнулся, в javascript. Это не основано на нерекурсивном надписи Кнута выше, хотя оно имеет некоторые сходства в элементарной свопинге. Я проверил его правильность для входных массивов до 8 элементов.

Быстрая оптимизация была бы предварительным вылетом массива и избежанием push() .

Основная идея:

1. Для одного исходного массива создайте первый новый набор массивов, которые поочередно меняют первый элемент с каждым последующим элементом, каждый раз оставляя остальные элементы невозмутимыми. например: с учетом 1234, генерировать 1234, 2134, 3214, 4231.

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

3. Повторите шаг 2 до завершения.

Вот пример кода:

 function oxe_perm(src, depth, index) { var perm = src.slice(); // duplicates src. perm = perm.split(""); perm[depth] = src[index]; perm[index] = src[depth]; perm = perm.join(""); return perm; } function oxe_permutations(src) { out = new Array(); out.push(src); for (depth = 0; depth < src.length; depth++) { var numInPreviousPass = out.length; for (var m = 0; m < numInPreviousPass; ++m) { for (var n = depth + 1; n < src.length; ++n) { out.push(oxe_perm(out[m], depth, n)); } } } return out; } 

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

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

Прежде чем вы войдете в свой цикл, инициализируйте Perm(1 To N) с первой перестановкой, Stack(3 To N) с нулями * и Level с 2 **. В конце цикла вызовите NextPerm , который вернет false, когда мы закончим.

* VB сделает это за вас.

** Вы можете немного изменить NextPerm, чтобы сделать это ненужным, но это более понятно.

 Option Explicit Function NextPerm(Perm() As Long, Stack() As Long, Level As Long) As Boolean Dim N As Long If Level = 2 Then Swap Perm(1), Perm(2) Level = 3 Else While Stack(Level) = Level - 1 Stack(Level) = 0 If Level = UBound(Stack) Then Exit Function Level = Level + 1 Wend Stack(Level) = Stack(Level) + 1 If Level And 1 Then N = 1 Else N = Stack(Level) Swap Perm(N), Perm(Level) Level = 2 End If NextPerm = True End Function Sub Swap(A As Long, B As Long) A = A Xor B B = A Xor B A = A Xor B End Sub 'This is just for testing. Private Sub Form_Paint() Const Max = 8 Dim A(1 To Max) As Long, I As Long Dim S(3 To Max) As Long, J As Long Dim Test As New Collection, T As String For I = 1 To UBound(A) A(I) = I Next Cls ScaleLeft = 0 J = 2 Do If CurrentY + TextHeight("0") > ScaleHeight Then ScaleLeft = ScaleLeft - TextWidth(" 0 ") * (UBound(A) + 1) CurrentY = 0 CurrentX = 0 End If T = vbNullString For I = 1 To UBound(A) Print A(I); T = T & Hex(A(I)) Next Print Test.Add Null, T Loop While NextPerm(A, S, J) J = 1 For I = 2 To UBound(A) J = J * I Next If J <> Test.Count Then Stop End Sub 

Другие методы описаны различными авторами. Кнут описывает два, один дает лексический порядок, но является сложным и медленным, другой известен как метод простых изменений. Цзе Гао и Дианджун Ван также написал интересную статью.

В rubyе:

 str = "a" 100_000_000.times {puts str.next!} 

Это довольно быстро, но это займет некоторое время =). Конечно, вы можете начать с «aaaaaaaa», если короткие строки вам не интересны.

Возможно, я неверно истолковал фактический вопрос – на одной из сообщений это звучало так, как будто вам просто нужна была строка с строкой strutforce, но в основном вопросе кажется, что вам нужно переставить определенную строку.

Ваша проблема несколько похожа на эту: http://beust.com/weblog/archives/000491.html (список всех целых чисел, в которых ни одна из цифр не повторяется, что привело к большому количеству языков, разрешающих ее, с ocaml guy, используя перестановки, и некоторый java-парень, использующий еще одно решение).

Этот код в python при вызове с allowed_characters установленными на [0,1] и 4 символа max, будет генерировать 2 ^ 4 результата:

['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']

 def generate_permutations(chars = 4) : #modify if in need! allowed_chars = [ '0', '1', ] status = [] for tmp in range(chars) : status.append(0) last_char = len(allowed_chars) rows = [] for x in xrange(last_char ** chars) : rows.append("") for y in range(chars - 1 , -1, -1) : key = status[y] rows[x] = allowed_chars[key] + rows[x] for pos in range(chars - 1, -1, -1) : if(status[pos] == last_char - 1) : status[pos] = 0 else : status[pos] += 1 break; return rows import sys print generate_permutations() 

Надеюсь, это вам полезно. Работает с любым персонажем, а не только с числами

Вот ссылка, которая описывает, как печатать перестановки строки. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Хотя это точно не отвечает на ваш вопрос, вот один из способов генерации каждой перестановки букв из нескольких строк одинаковой длины: например, если ваши слова были «кофе», «joomla» и «moodle», вы можете ожидайте выхода, например, «coodle», «joodee», «joffle» и т. д.

В принципе, количество комбинаций – это количество слов (количество слов) в степени (количество букв на слово). Итак, выберите случайное число между 0 и числом комбинаций – 1, преобразуйте это число в базу (количество слов), затем используйте каждую цифру этого числа в качестве индикатора, из которого слово берет следующую букву.

например: в приведенном выше примере. 3 слова, 6 букв = 729 комбинаций. Выберите случайное число: 465. Преобразуйте на базу 3: 122020. Возьмите первую букву из слова 1, 2-й из слова 2, 3-го из слова 2, 4-го из слова 0 … и получите … «joofle».

Если вы хотите все перестановки, просто зациклируйте от 0 до 728. Конечно, если вы просто выбираете одно случайное значение, гораздо проще, чем запутывать, было бы перебирать буквы. Этот метод позволяет избежать рекурсии, если вы хотите все перестановки, плюс это заставляет вас выглядеть так, как вы знаете, Maths ^(tm) !

Если количество комбинаций является чрезмерным, вы можете разбить его на ряд меньших слов и объединить их в конце.

c # итеративный:

 public List Permutations(char[] chars) { List words = new List(); words.Add(chars[0].ToString()); for (int i = 1; i < chars.Length; ++i) { int currLen = words.Count; for (int j = 0; j < currLen; ++j) { var w = words[j]; for (int k = 0; k <= w.Length; ++k) { var nstr = w.Insert(k, chars[i].ToString()); if (k == 0) words[j] = nstr; else words.Add(nstr); } } } return words; } 

Существует итеративная реализация Java в UncommonsMaths (работает для списка объектов):

 /** * Generate the indices into the elements array for the next permutation. The * algorithm is from Kenneth H. Rosen, Discrete Mathematics and its * Applications, 2nd edition (NY: McGraw-Hill, 1991), p. 284) */ private void generateNextPermutationIndices() { if (remainingPermutations == 0) { throw new IllegalStateException("There are no permutations " + "remaining. Generator must be reset to continue using."); } else if (remainingPermutations < totalPermutations) { // Find largest index j with // permutationIndices[j] < permutationIndices[j + 1] int j = permutationIndices.length - 2; while (permutationIndices[j] > permutationIndices[j + 1]) { j--; } // Find index k such that permutationIndices[k] is smallest integer // greater than permutationIndices[j] to the right // of permutationIndices[j]. int k = permutationIndices.length - 1; while (permutationIndices[j] > permutationIndices[k]) { k--; } // Interchange permutation indices. int temp = permutationIndices[k]; permutationIndices[k] = permutationIndices[j]; permutationIndices[j] = temp; // Put tail end of permutation after jth position in increasing order. int r = permutationIndices.length - 1; int s = j + 1; while (r > s) { temp = permutationIndices[s]; permutationIndices[s] = permutationIndices[r]; permutationIndices[r] = temp; r--; s++; } } --remainingPermutations; } /** * Generate the next permutation and return a list containing * the elements in the appropriate order. This overloaded method * allows the caller to provide a list that will be used and returned. * The purpose of this is to improve performance when iterating over * permutations. If the {@link #nextPermutationAsList()} method is * used it will create a new list every time. When iterating over * permutations this will result in lots of short-lived objects that * have to be garbage collected. This method allows a single list * instance to be reused in such circumstances. * @param destination Provides a list to use to create the * permutation. This is the list that will be returned, once * it has been filled with the elements in the appropriate order. * @return The next permutation as a list. */ public List nextPermutationAsList(List destination) { generateNextPermutationIndices(); // Generate actual permutation. destination.clear(); for (int i : permutationIndices) { destination.add(elements[i]); } return destination; } 

Полный источник

 def gen( x,y,list): #to generate all strings inserting y at different positions list = [] list.append( y+x ) for i in range( len(x) ): list.append( func(x,0,i) + y + func(x,i+1,len(x)-1) ) return list def func( x,i,j ): #returns x[i..j] z = '' for i in range(i,j+1): z = z+x[i] return z def perm( x , length , list ): #perm function if length == 1 : # base case list.append( x[len(x)-1] ) return list else: lists = perm( x , length-1 ,list ) lists_temp = lists #temporarily storing the list lists = [] for i in range( len(lists_temp) ) : list_temp = gen(lists_temp[i],x[length-2],lists) lists += list_temp return lists 

 def permutation(str) posibilities = [] str.split('').each do |char| if posibilities.size == 0 posibilities[0] = char.downcase posibilities[1] = char.upcase else posibilities_count = posibilities.length posibilities = posibilities + posibilities posibilities_count.times do |i| posibilities[i] += char.downcase posibilities[i+posibilities_count] += char.upcase end end end posibilities end максимальные def permutation(str) posibilities = [] str.split('').each do |char| if posibilities.size == 0 posibilities[0] = char.downcase posibilities[1] = char.upcase else posibilities_count = posibilities.length posibilities = posibilities + posibilities posibilities_count.times do |i| posibilities[i] += char.downcase posibilities[i+posibilities_count] += char.upcase end end end posibilities end 

Вот мой вопрос о нерекурсивной версии

Питоновское решение:

 from itertools import permutations s = 'ABCDEF' p = [''.join(x) for x in permutations(s)]