生成给定string的所有排列

什么是一个优雅的方式来find一个string的所有排列。 例如ba ，会是ba和ab ，但是abcdefgh呢？ 有没有任何Java实现的例子？

Answer 1

 public static void permutation(String str) { permutation("", str); } private static void permutation(String prefix, String str) { int n = str.length(); if (n == 0) System.out.println(prefix); else { for (int i = 0; i < n; i++) permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)); } } 

（通过Java编程入门 ）

Answer 2

使用recursion。

• 依次尝试每个字母作为第一个字母，然后使用recursion调用查找其余字母的所有排列。
• 基本情况是当input是空string时，唯一的排列是空string。

Answer 3

这是我的解决scheme，是基于“破解编码访谈”（P54）的想法：

 /** * List permutation of a string * * @param s the input string * @return the list of permutation */ public static ArrayList<String> permutation(String s) { // The result ArrayList<String> res = new ArrayList<String>(); // If input string's length is 1, return {s} if (s.length() == 1) { res.add(s); } else if (s.length() > 1) { int lastIndex = s.length() - 1; // Find out the last character String last = s.substring(lastIndex); // Rest of the string String rest = s.substring(0, lastIndex); // Perform permutation on the rest string and // merge with the last character res = merge(permutation(rest), last); } return res; } /** * @param list a result of permutation, eg {"ab", "ba"} * @param c the last character * @return a merged new list, eg {"cab", "acb" ... } */ public static ArrayList<String> merge(ArrayList<String> list, String c) { ArrayList<String> res = new ArrayList<String>(); // Loop through all the string in the list for (String s : list) { // For each string, insert the last character to all possible postions // and add them to the new list for (int i = 0; i <= s.length(); ++i) { String ps = new StringBuffer(s).insert(i, c).toString(); res.add(ps); } } return res; } 

---

运行string“abcd”的输出：

• 步骤1：合并[a]和b：[ba，ab]

• 步骤2：合并[ba，ab]和c：[cba，bca，bac，cab，acb，abc]

• 步骤3：合并[cba，bca，bac，cab，acb，abc]和d：[dcba，cdba，cbda，cbad，dbca，bdca，bcda，bcad，dbac，bdac，badc，bacd，dcab，cdab，cadb ，cabd，dacb，adcb，acdb，acbd，dabc，adbc，abdc，abcd]

Answer 4

在这里和其他论坛给出的所有解决scheme中，我最喜欢马克·拜尔斯（Mark Byers）。 这个描述实际上让我自己思考和编码。 太糟糕了，我不能投票他的解决scheme，因为我是新手。 无论如何，这里是我的执行他的描述

 public class PermTest { public static void main(String[] args) throws Exception { String str = "abcdef"; StringBuffer strBuf = new StringBuffer(str); doPerm(strBuf,str.length()); } private static void doPerm(StringBuffer str, int index){ if(index <= 0) System.out.println(str); else { //recursively solve this by placing all other chars at current first pos doPerm(str, index-1); int currPos = str.length()-index; for (int i = currPos+1; i < str.length(); i++) {//start swapping all other chars with current first char swap(str,currPos, i); doPerm(str, index-1); swap(str,i, currPos);//restore back my string buffer } } } private static void swap(StringBuffer str, int pos1, int pos2){ char t1 = str.charAt(pos1); str.setCharAt(pos1, str.charAt(pos2)); str.setCharAt(pos2, t1); } } 

我更喜欢这个解决scheme之前在这个线程中的第一个，因为这个解决scheme使用StringBuffer.I不会说我的解决scheme不会创build任何临时string（它实际上在system.out.println其中的toString（）的StringBuffer所谓的）。 但我只是觉得这比创build太多string文字的第一个解决scheme要好。 可能是一些performance家伙可以根据“记忆”来评估这一点（对于“时间”而言，由于额外的“交换”，它已经落后了）

Answer 5

Java中一个非常基本的解决scheme是使用recursion+ Set（避免重复），如果你想存储并返回解决schemestring：

 public static Set<String> generatePerm(String input) { Set<String> set = new HashSet<String>(); if (input == "") return set; Character a = input.charAt(0); if (input.length() > 1) { input = input.substring(1); Set<String> permSet = generatePerm(input); for (String x : permSet) { for (int i = 0; i <= x.length(); i++) { set.add(x.substring(0, i) + a + x.substring(i)); } } } else { set.add(a + ""); } return set; } 

Answer 6

所有以前的贡献者都做了很好的解释和提供代码。 我以为我也应该分享这个方法，因为它也可以帮助别人。 该解决scheme基于（ 堆algorithm ）

几件事：

1. 注意在excel中描述的最后一个项目只是为了帮助您更好地理解逻辑。 所以，最后一列的实际值将是2,1,0（如果我们要运行代码，因为我们正在处理数组，数组以0开头）。

2. 交换algorithm基于当前位置的偶数或奇数值而发生。 如果你看看交换方法被调用的地方，这是非常明显的。你可以看到发生了什么事情。

这是发生了什么事情：

 public static void main(String[] args) { String ourword = "abc"; String[] ourArray = ourword.split(""); permute(ourArray, ourArray.length); } private static void swap(String[] ourarray, int right, int left) { String temp = ourarray[right]; ourarray[right] = ourarray[left]; ourarray[left] = temp; } public static void permute(String[] ourArray, int currentPosition) { if (currentPosition == 1) { System.out.println(Arrays.toString(ourArray)); } else { for (int i = 0; i < currentPosition; i++) { // subtract one from the last position (here is where you are // selecting the the next last item permute(ourArray, currentPosition - 1); // if it's odd position if (currentPosition % 2 == 1) { swap(ourArray, 0, currentPosition - 1); } else { swap(ourArray, i, currentPosition - 1); } } } } 

Answer 7

这一个没有recursion

 public static void permute(String s) { if(null==s || s.isEmpty()) { return; } // List containing words formed in each iteration List<String> strings = new LinkedList<String>(); strings.add(String.valueOf(s.charAt(0))); // add the first element to the list // Temp list that holds the set of strings for // appending the current character to all position in each word in the original list List<String> tempList = new LinkedList<String>(); for(int i=1; i< s.length(); i++) { for(int j=0; j<strings.size(); j++) { tempList.addAll(merge(s.charAt(i), strings.get(j))); } strings.removeAll(strings); strings.addAll(tempList); tempList.removeAll(tempList); } for(int i=0; i<strings.size(); i++) { System.out.println(strings.get(i)); } } /** * helper method that appends the given character at each position in the given string * and returns a set of such modified strings * - set removes duplicates if any(in case a character is repeated) */ private static Set<String> merge(Character c, String s) { if(s==null || s.isEmpty()) { return null; } int len = s.length(); StringBuilder sb = new StringBuilder(); Set<String> list = new HashSet<String>(); for(int i=0; i<= len; i++) { sb = new StringBuilder(); sb.append(s.substring(0, i) + c + s.substring(i, len)); list.add(sb.toString()); } return list; } 

Answer 8

我们以inputabc为例。

从集合（ ["c"] ）中的最后一个元素（ c ）开始，然后将第二个元素（ b ）添加到它的前面，结尾和中间的每个可能位置，使其成为["bc", "cb"] ，然后以相同的方式将后面的（ a ）中的下一个元素添加到集合中的每个string中：

 "a" + "bc" = ["abc", "bac", "bca"] and "a" + "cb" = ["acb" ,"cab", "cba"] 

这样整个排列：

 ["abc", "bac", "bca","acb" ,"cab", "cba"] 

码：

 public class Test { static Set<String> permutations; static Set<String> result = new HashSet<String>(); public static Set<String> permutation(String string) { permutations = new HashSet<String>(); int n = string.length(); for (int i = n - 1; i >= 0; i--) { shuffle(string.charAt(i)); } return permutations; } private static void shuffle(char c) { if (permutations.size() == 0) { permutations.add(String.valueOf(c)); } else { Iterator<String> it = permutations.iterator(); for (int i = 0; i < permutations.size(); i++) { String temp1; for (; it.hasNext();) { temp1 = it.next(); for (int k = 0; k < temp1.length() + 1; k += 1) { StringBuilder sb = new StringBuilder(temp1); sb.insert(k, c); result.add(sb.toString()); } } } permutations = result; //'result' has to be refreshed so that in next run it doesn't contain stale values. result = new HashSet<String>(); } } public static void main(String[] args) { Set<String> result = permutation("abc"); System.out.println("\nThere are total of " + result.size() + " permutations:"); Iterator<String> it = result.iterator(); while (it.hasNext()) { System.out.println(it.next()); } } } 

Answer 9

那么这里是一个优雅的，非recursion的O（n！）解决scheme：

 public static StringBuilder[] permutations(String s) { if (s.length() == 0) return null; int length = fact(s.length()); StringBuilder[] sb = new StringBuilder[length]; for (int i = 0; i < length; i++) { sb[i] = new StringBuilder(); } for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); int times = length / (i + 1); for (int j = 0; j < times; j++) { for (int k = 0; k < length / times; k++) { sb[j * length / times + k].insert(k, ch); } } } return sb; } 

Answer 10

其中一个简单的解决scheme可能是使用两个指针recursion交换字符。

 public static void main(String[] args) { String str="abcdefgh"; perm(str); } public static void perm(String str) { char[] char_arr=str.toCharArray(); helper(char_arr,0); } public static void helper(char[] char_arr, int i) { if(i==char_arr.length-1) { // print the shuffled string String str=""; for(int j=0; j<char_arr.length; j++) { str=str+char_arr[j]; } System.out.println(str); } else { for(int j=i; j<char_arr.length; j++) { char tmp = char_arr[i]; char_arr[i] = char_arr[j]; char_arr[j] = tmp; helper(char_arr,i+1); char tmp1 = char_arr[i]; char_arr[i] = char_arr[j]; char_arr[j] = tmp1; } } } 

Answer 11

使用recursion。

当input是一个空string时，唯一的排列是一个空string。将string中的每个字母作为第一个字母，然后使用recursion调用来查找其余字母的所有排列。

 import java.util.ArrayList; import java.util.List; class Permutation { private static List<String> permutation(String prefix, String str) { List<String> permutations = new ArrayList<>(); int n = str.length(); if (n == 0) { permutations.add(prefix); } else { for (int i = 0; i < n; i++) { permutations.addAll(permutation(prefix + str.charAt(i), str.substring(i + 1, n) + str.substring(0, i))); } } return permutations; } public static void main(String[] args) { List<String> perms = permutation("", "abcd"); String[] array = new String[perms.size()]; for (int i = 0; i < perms.size(); i++) { array[i] = perms.get(i); } int x = array.length; for (final String anArray : array) { System.out.println(anArray); } } } 

Answer 12

这对我工作..

 import java.util.Arrays; public class StringPermutations{ public static void main(String args[]) { String inputString = "ABC"; permute(inputString.toCharArray(), 0, inputString.length()-1); } public static void permute(char[] ary, int startIndex, int endIndex) { if(startIndex == endIndex){ System.out.println(String.valueOf(ary)); }else{ for(int i=startIndex;i<=endIndex;i++) { swap(ary, startIndex, i ); permute(ary, startIndex+1, endIndex); swap(ary, startIndex, i ); } } } public static void swap(char[] ary, int x, int y) { char temp = ary[x]; ary[x] = ary[y]; ary[y] = temp; } } 

Answer 13

python实现

 def getPermutation(s, prefix=''): if len(s) == 0: print prefix for i in range(len(s)): getPermutation(s[0:i]+s[i+1:len(s)],prefix+s[i] ) getPermutation('abcd','') 

Answer 14

 import java.io.IOException; import java.util.ArrayList; import java.util.Scanner; public class hello { public static void main(String[] args) throws IOException { hello h = new hello(); h.printcomp(); } int fact=1; public void factrec(int a,int k){ if(a>=k) {fact=fact*k; k++; factrec(a,k); } else {System.out.println("The string will have "+fact+" permutations"); } } public void printcomp(){ String str; int k; Scanner in = new Scanner(System.in); System.out.println("enter the string whose permutations has to b found"); str=in.next(); k=str.length(); factrec(k,1); String[] arr =new String[fact]; char[] array = str.toCharArray(); while(p<fact) printcomprec(k,array,arr); // if incase u need array containing all the permutation use this //for(int d=0;d<fact;d++) //System.out.println(arr[d]); } int y=1; int p = 0; int g=1; int z = 0; public void printcomprec(int k,char array[],String arr[]){ for (int l = 0; l < k; l++) { for (int b=0;b<k-1;b++){ for (int i=1; i<kg; i++) { char temp; String stri = ""; temp = array[i]; array[i] = array[i + g]; array[i + g] = temp; for (int j = 0; j < k; j++) stri += array[j]; arr[z] = stri; System.out.println(arr[z] + " " + p++); z++; } } char temp; temp=array[0]; array[0]=array[y]; array[y]=temp; if (y >= k-1) y=y-(k-1); else y++; } if (g >= k-1) g=1; else g++; } } 

Answer 15

 /** Returns an array list containing all * permutations of the characters in s. */ public static ArrayList<String> permute(String s) { ArrayList<String> perms = new ArrayList<>(); int slen = s.length(); if (slen > 0) { // Add the first character from s to the perms array list. perms.add(Character.toString(s.charAt(0))); // Repeat for all additional characters in s. for (int i = 1; i < slen; ++i) { // Get the next character from s. char c = s.charAt(i); // For each of the strings currently in perms do the following: int size = perms.size(); for (int j = 0; j < size; ++j) { // 1. remove the string String p = perms.remove(0); int plen = p.length(); // 2. Add plen + 1 new strings to perms. Each new string // consists of the removed string with the character c // inserted into it at a unique location. for (int k = 0; k <= plen; ++k) { perms.add(p.substring(0, k) + c + p.substring(k)); } } } } return perms; } 

Answer 16

在Java中，这是一个简单的极简主义recursion解决scheme：

 public static ArrayList<String> permutations(String s) { ArrayList<String> out = new ArrayList<String>(); if (s.length() == 1) { out.add(s); return out; } char first = s.charAt(0); String rest = s.substring(1); for (String permutation : permutations(rest)) { out.addAll(insertAtAllPositions(first, permutation)); } return out; } public static ArrayList<String> insertAtAllPositions(char ch, String s) { ArrayList<String> out = new ArrayList<String>(); for (int i = 0; i <= s.length(); ++i) { String inserted = s.substring(0, i) + ch + s.substring(i); out.add(inserted); } return out; } 

Answer 17

这是我通过对排列和recursion函数调用的基本理解所做的。 需要一点时间，但它是独立完成的。

 public class LexicographicPermutations { public static void main(String[] args) { // TODO Auto-generated method stub String s="abc"; List<String>combinations=new ArrayList<String>(); combinations=permutations(s); Collections.sort(combinations); System.out.println(combinations); } private static List<String> permutations(String s) { // TODO Auto-generated method stub List<String>combinations=new ArrayList<String>(); if(s.length()==1){ combinations.add(s); } else{ for(int i=0;i<s.length();i++){ List<String>temp=permutations(s.substring(0, i)+s.substring(i+1)); for (String string : temp) { combinations.add(s.charAt(i)+string); } } } return combinations; }} 

生成输出为[abc, acb, bac, bca, cab, cba] 。

它背后的基本逻辑是

对于每个字符，将其视为第一个字符并查找剩余字符的组合。 例如[abc](Combination of abc)-> 。

1. a->[bc](ax Combination of (bc))->{abc,acb}
2. b->[ac](bx Combination of (ac))->{bac,bca}
3. c->[ab](cx Combination of (ab))->{cab,cba}

然后分别recursion地调用每个[bc] ， [ac] ＆ [ab] 。

Answer 18

 //Rotate and create words beginning with all letter possible and push to stack 1 //Read from stack1 and for each word create words with other letters at the next location by rotation and so on /* eg : man 1. push1 - man, anm, nma 2. pop1 - nma , push2 - nam,nma pop1 - anm , push2 - amn,anm pop1 - man , push2 - mna,man */ public class StringPermute { static String str; static String word; static int top1 = -1; static int top2 = -1; static String[] stringArray1; static String[] stringArray2; static int strlength = 0; public static void main(String[] args) throws IOException { System.out.println("Enter String : "); InputStreamReader isr = new InputStreamReader(System.in); BufferedReader bfr = new BufferedReader(isr); str = bfr.readLine(); word = str; strlength = str.length(); int n = 1; for (int i = 1; i <= strlength; i++) { n = n * i; } stringArray1 = new String[n]; stringArray2 = new String[n]; push(word, 1); doPermute(); display(); } public static void push(String word, int x) { if (x == 1) stringArray1[++top1] = word; else stringArray2[++top2] = word; } public static String pop(int x) { if (x == 1) return stringArray1[top1--]; else return stringArray2[top2--]; } public static void doPermute() { for (int j = strlength; j >= 2; j--) popper(j); } public static void popper(int length) { // pop from stack1 , rotate each word n times and push to stack 2 if (top1 > -1) { while (top1 > -1) { word = pop(1); for (int j = 0; j < length; j++) { rotate(length); push(word, 2); } } } // pop from stack2 , rotate each word n times wrt position and push to // stack 1 else { while (top2 > -1) { word = pop(2); for (int j = 0; j < length; j++) { rotate(length); push(word, 1); } } } } public static void rotate(int position) { char[] charstring = new char[100]; for (int j = 0; j < word.length(); j++) charstring[j] = word.charAt(j); int startpos = strlength - position; char temp = charstring[startpos]; for (int i = startpos; i < strlength - 1; i++) { charstring[i] = charstring[i + 1]; } charstring[strlength - 1] = temp; word = new String(charstring).trim(); } public static void display() { int top; if (top1 > -1) { while (top1 > -1) System.out.println(stringArray1[top1--]); } else { while (top2 > -1) System.out.println(stringArray2[top2--]); } } } 

Answer 19

我们可以使用factorial来查找以特定字母开头的string数量。

例如：inputabcd 。 (3!) == 6string将以abcd每个字母开始。

 static public int facts(int x){ int sum = 1; for (int i = 1; i < x; i++) { sum *= (i+1); } return sum; } public static void permutation(String str) { char[] str2 = str.toCharArray(); int n = str2.length; int permutation = 0; if (n == 1) { System.out.println(str2[0]); } else if (n == 2) { System.out.println(str2[0] + "" + str2[1]); System.out.println(str2[1] + "" + str2[0]); } else { for (int i = 0; i < n; i++) { if (true) { char[] str3 = str.toCharArray(); char temp = str3[i]; str3[i] = str3[0]; str3[0] = temp; str2 = str3; } for (int j = 1, count = 0; count < facts(n-1); j++, count++) { if (j != n-1) { char temp1 = str2[j+1]; str2[j+1] = str2[j]; str2[j] = temp1; } else { char temp1 = str2[n-1]; str2[n-1] = str2[1]; str2[1] = temp1; j = 1; } // end of else block permutation++; System.out.print("permutation " + permutation + " is -> "); for (int k = 0; k < n; k++) { System.out.print(str2[k]); } // end of loop k System.out.println(); } // end of loop j } // end of loop i } } 

Answer 20

这是一个Java实现：

 /* All Permutations of a String */ import java.util.*; import java.lang.*; import java.io.*; /* Complexity O(n*n!) */ class Ideone { public static ArrayList<String> strPerm(String str, ArrayList<String> list) { int len = str.length(); if(len==1){ list.add(str); return list; } list = strPerm(str.substring(0,len-1),list); int ls = list.size(); char ap = str.charAt(len-1); for(int i=0;i<ls;i++){ String temp = list.get(i); int tl = temp.length(); for(int j=0;j<=tl;j++){ list.add(temp.substring(0,j)+ap+temp.substring(j,tl)); } } while(true){ String temp = list.get(0); if(temp.length()<len) list.remove(temp); else break; } return list; } public static void main (String[] args) throws java.lang.Exception { String str = "abc"; ArrayList<String> list = new ArrayList<>(); list = strPerm(str,list); System.out.println("Total Permutations : "+list.size()); for(int i=0;i<list.size();i++) System.out.println(list.get(i)); } } 

http://ideone.com/nWPb3k

Answer 21

recursion是没有必要的，即使你可以直接计算任何排列 ，这个解决scheme使用generics来排列任何数组。

这是关于这个algorithm的一个很好的信息。

对于C＃开发人员来说， 这是更有用的实现。

 public static void main(String[] args) { String word = "12345"; Character[] array = ArrayUtils.toObject(word.toCharArray()); long[] factorials = Permutation.getFactorials(array.length + 1); for (long i = 0; i < factorials[array.length]; i++) { Character[] permutation = Permutation.<Character>getPermutation(i, array, factorials); printPermutation(permutation); } } private static void printPermutation(Character[] permutation) { for (int i = 0; i < permutation.length; i++) { System.out.print(permutation[i]); } System.out.println(); } 

该algorithm具有O（N） 时间和空间复杂度来计算每个排列 。

 public class Permutation { public static <T> T[] getPermutation(long permutationNumber, T[] array, long[] factorials) { int[] sequence = generateSequence(permutationNumber, array.length - 1, factorials); T[] permutation = generatePermutation(array, sequence); return permutation; } public static <T> T[] generatePermutation(T[] array, int[] sequence) { T[] clone = array.clone(); for (int i = 0; i < clone.length - 1; i++) { swap(clone, i, i + sequence[i]); } return clone; } private static int[] generateSequence(long permutationNumber, int size, long[] factorials) { int[] sequence = new int[size]; for (int j = 0; j < sequence.length; j++) { long factorial = factorials[sequence.length - j]; sequence[j] = (int) (permutationNumber / factorial); permutationNumber = (int) (permutationNumber % factorial); } return sequence; } private static <T> void swap(T[] array, int i, int j) { T t = array[i]; array[i] = array[j]; array[j] = t; } public static long[] getFactorials(int length) { long[] factorials = new long[length]; long factor = 1; for (int i = 0; i < length; i++) { factor *= i <= 1 ? 1 : i; factorials[i] = factor; } return factorials; } } 

Answer 22

没有recursion的Java实现

 public Set<String> permutate(String s){ Queue<String> permutations = new LinkedList<String>(); Set<String> v = new HashSet<String>(); permutations.add(s); while(permutations.size()!=0){ String str = permutations.poll(); if(!v.contains(str)){ v.add(str); for(int i = 0;i<str.length();i++){ String c = String.valueOf(str.charAt(i)); permutations.add(str.substring(i+1) + c + str.substring(0,i)); } } } return v; } 

Answer 23

//将每个字符插入一个数组列表

 static ArrayList al = new ArrayList(); private static void findPermutation (String str){ for (int k = 0; k < str.length(); k++) { addOneChar(str.charAt(k)); } } //insert one char into ArrayList private static void addOneChar(char ch){ String lastPerStr; String tempStr; ArrayList locAl = new ArrayList(); for (int i = 0; i < al.size(); i ++ ){ lastPerStr = al.get(i).toString(); //System.out.println("lastPerStr: " + lastPerStr); for (int j = 0; j <= lastPerStr.length(); j++) { tempStr = lastPerStr.substring(0,j) + ch + lastPerStr.substring(j, lastPerStr.length()); locAl.add(tempStr); //System.out.println("tempStr: " + tempStr); } } if(al.isEmpty()){ al.add(ch); } else { al.clear(); al = locAl; } } private static void printArrayList(ArrayList al){ for (int i = 0; i < al.size(); i++) { System.out.print(al.get(i) + " "); } } 

Answer 24

改进的代码相同

  static String permutationStr[]; static int indexStr = 0; static int factorial (int i) { if (i == 1) return 1; else return i * factorial(i-1); } public static void permutation(String str) { char strArr[] = str.toLowerCase().toCharArray(); java.util.Arrays.sort(strArr); int count = 1, dr = 1; for (int i = 0; i < strArr.length-1; i++){ if ( strArr[i] == strArr[i+1]) { count++; } else { dr *= factorial(count); count = 1; } } dr *= factorial(count); count = factorial(strArr.length) / dr; permutationStr = new String[count]; permutation("", str); for (String oneStr : permutationStr){ System.out.println(oneStr); } } private static void permutation(String prefix, String str) { int n = str.length(); if (n == 0) { for (int i = 0; i < indexStr; i++){ if(permutationStr[i].equals(prefix)) return; } permutationStr[indexStr++] = prefix; } else { for (int i = 0; i < n; i++) { permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n)); } } } 

Answer 25

 /* * eg: abc =>{a,bc},{b,ac},{c,ab} * =>{ca,b},{cb,a} * =>cba,cab * =>{ba,c},{bc,a} * =>bca,bac * =>{ab,c},{ac,b} * =>acb,abc */ public void nonRecpermute(String prefix, String word) { String[] currentstr ={prefix,word}; Stack<String[]> stack = new Stack<String[]>(); stack.add(currentstr); while(!stack.isEmpty()) { currentstr = stack.pop(); String currentPrefix = currentstr[0]; String currentWord = currentstr[1]; if(currentWord.equals("")) { System.out.println("Word ="+currentPrefix); } for(int i=0;i<currentWord.length();i++) { String[] newstr = new String[2]; newstr[0]=currentPrefix + String.valueOf(currentWord.charAt(i)); newstr[1] = currentWord.substring(0, i); if(i<currentWord.length()-1) { newstr[1] = newstr[1]+currentWord.substring(i+1); } stack.push(newstr); } } } 

Answer 26

这可以通过在前面的部分结果的所有位置依次插入string的每个字母来迭代地完成。

我们从[A]开始，与B成为[BA, AB]和C ， [CBA, BCA, BAC, CAB, etc] 。

运行时间为O(n!) ，对于testing用例ABCD ，运行时间为1 x 2 x 3 x 4 。

在上面的产品中， 1是A ， 2是B等。

飞镖样本：

 void main() { String insertAt(String a, String b, int index) { return a.substring(0, index) + b + a.substring(index); } List<String> Permute(String word) { var letters = word.split(''); var p_list = [ letters.first ]; for (var c in letters.sublist(1)) { var new_list = [ ]; for (var p in p_list) for (int i = 0; i <= p.length; i++) new_list.add(insertAt(p, c, i)); p_list = new_list; } return p_list; } print(Permute("ABCD")); } 

Answer 27

这里有两个C＃版本（仅供参考）：1.打印所有permuations 2.返回所有排列

该algorithm的基本要点是（可能下面的代码更直观 – 不过，这里是对下面代码做什么的一些解释）： – 从当前索引到剩下的集合，交换当前索引处的元素 – 获取排列对于来自下一个索引的其余元素recursion地 – 通过重新交换恢复顺序

注意：上面的recursion函数将从start索引被调用。

 private void PrintAllPermutations(int[] a, int index, ref int count) { if (index == (a.Length - 1)) { count++; var s = string.Format("{0}: {1}", count, string.Join(",", a)); Debug.WriteLine(s); } for (int i = index; i < a.Length; i++) { Utilities.swap(ref a[i], ref a[index]); this.PrintAllPermutations(a, index + 1, ref count); Utilities.swap(ref a[i], ref a[index]); } } private int PrintAllPermutations(int[] a) { a.ThrowIfNull("a"); int count = 0; this.PrintAllPermutations(a, index:0, count: ref count); return count; } 

版本2（与上面相同 – 但返回排列代替打印）

 private int[][] GetAllPermutations(int[] a, int index) { List<int[]> permutations = new List<int[]>(); if (index == (a.Length - 1)) { permutations.Add(a.ToArray()); } for (int i = index; i < a.Length; i++) { Utilities.swap(ref a[i], ref a[index]); var r = this.GetAllPermutations(a, index + 1); permutations.AddRange(r); Utilities.swap(ref a[i], ref a[index]); } return permutations.ToArray(); } private int[][] GetAllPermutations(int[] p) { p.ThrowIfNull("p"); return this.GetAllPermutations(p, 0); } 

unit testing

 [TestMethod] public void PermutationsTests() { List<int> input = new List<int>(); int[] output = { 0, 1, 2, 6, 24, 120 }; for (int i = 0; i <= 5; i++) { if (i != 0) { input.Add(i); } Debug.WriteLine("================PrintAllPermutations==================="); int count = this.PrintAllPermutations(input.ToArray()); Assert.IsTrue(count == output[i]); Debug.WriteLine("=====================GetAllPermutations================="); var r = this.GetAllPermutations(input.ToArray()); Assert.IsTrue(count == r.Length); for (int j = 1; j <= r.Length;j++ ) { string s = string.Format("{0}: {1}", j, string.Join(",", r[j - 1])); Debug.WriteLine(s); } Debug.WriteLine("No.OfElements: {0}, TotalPerms: {1}", i, count); } } 

Answer 28

Another simple way is to loop through the string, pick the character that is not used yet and put it to a buffer, continue the loop till the buffer size equals to the string length. I like this back tracking solution better because:

1. 容易明白
2. Easy to avoid duplication
3. The output is sorted

Here is the java code:

 List<String> permute(String str) { if (str == null) { return null; } char[] chars = str.toCharArray(); boolean[] used = new boolean[chars.length]; List<String> res = new ArrayList<String>(); StringBuilder sb = new StringBuilder(); Arrays.sort(chars); helper(chars, used, sb, res); return res; } void helper(char[] chars, boolean[] used, StringBuilder sb, List<String> res) { if (sb.length() == chars.length) { res.add(sb.toString()); return; } for (int i = 0; i < chars.length; i++) { // avoid duplicates if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) { continue; } // pick the character that has not used yet if (!used[i]) { used[i] = true; sb.append(chars[i]); helper(chars, used, sb, res); // back tracking sb.deleteCharAt(sb.length() - 1); used[i] = false; } } } 

Input str: 1231

Output list: {1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211}

Noticed that the output is sorted, and there is no duplicate result.

Answer 29

This is a C solution:

 #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> char* addLetter(char* string, char *c) { char* result = malloc(sizeof(string) + 2); strcpy(result, string); strncat(result, c, 1); return result; } char* removeLetter(char* string, char *c) { char* result = malloc(sizeof(string)); int j = 0; for (int i = 0; i < strlen(string); i++) { if (string[i] != *c) { result[j++] = string[i]; } } result[j] = '\0'; return result; } void makeAnagram(char *anagram, char *letters) { if (*letters == '\0') { printf("%s\n", anagram); return; } char *c = letters; while (*c != '\0') { makeAnagram(addLetter(anagram, c), removeLetter(letters, c)); c++; } } int main() { makeAnagram("", "computer"); return 0; } 

Answer 30

My implementation based on Mark Byers's description above:

  static Set<String> permutations(String str){ if (str.isEmpty()){ return Collections.singleton(str); }else{ Set <String> set = new HashSet<>(); for (int i=0; i<str.length(); i++) for (String s : permutations(str.substring(0, i) + str.substring(i+1))) set.add(str.charAt(i) + s); return set; } }