Reference：
http://www.cnblogs.com/sujz/archive/2011/06/16/2082831.html
问题：给定字符串S，生成该字符串的全排列。
方法1：依次从字符串中取出一个字符作为最终排列的第一个字符，对剩余字符组成的字符串生成全排列，最终结果为取出的字符和剩余子串全排列的组合。
public static void main(String[] args) {
Main so = new Main();
System.out.println("method 1:");
so.permutation("","ABA");
}
public void permutation(String prefix,String s){
if(s==null||s.length()==0)
System.out.println(prefix);
for(int i=0;i<s.length();i++){
permutation(prefix+s.charAt(i), s.substring(0, i)+s.substring(i+1,s.length()));
}
}
优点：该方法易于理解，但无法移除重复的排列，如：s="ABA"，会生成两个“AAB”。
method 1:
ABA
AAB
BAA
BAA
AAB
ABA
方法2：利用交换的思想，具体见实例，但该方法不如方法1容易理解。
package POJ;
import java.util.HashMap;
public class Main {
/**
*
* 9.4 Write a method to compute all permutations of a string.
*
*
*/
public static void main(String[] args) {
Main so = new Main();
System.out.println("method 2:");
HashMap<String, Integer> hs=new HashMap<String, Integer>();
so.permutation2("AABB", 0, 3,hs);
}
public void permutation2(String s, int startIndex, int endIndex,HashMap<String, Integer> hs) {
if (startIndex == endIndex) {
if(!hs.containsKey(s)){
hs.put(s, 1);
System.out.println(s);
}
}
for (int j = startIndex; j <= endIndex; j++) {
if ((s.charAt(j) == s.charAt(startIndex)) && (j != startIndex))
continue;
s = swap(s, startIndex, j);
permutation2(s, startIndex + 1, endIndex,hs);
s = swap(s, startIndex, j);
}
}
public String swap(String s, int i, int j) {
char[] char_s = s.toCharArray();
char temp = char_s[i];
char_s[i] = char_s[j];
char_s[j] = temp;
s = String.copyValueOf(char_s);
return s;
}
}
运行结果：
method 2:
AABB
ABAB
ABBA
BAAB
BABA
BBAA
原Reference里的那个哥们儿的代码有点问题，他的代码用java实现后只能完成类似于ABCD,AABC等string的无重复全排列，而无法做到AABB这种类型的无重复全排列。