簡介：
本文主要介紹基于分治方式（遞歸）和枚舉方式（循環）來建構指定字元串的全排列方法，兩種方法都可以解決重複元素的全排列
歡迎探讨，如有錯誤敬請指正
如需轉載，請注明出處 http://www.cnblogs.com/nullzx/
1. 基于分治方式（遞歸實作）
1）一個元素的全排列隻有一種
2）[A0, A1, A2]的全排列等于下面三個全排列的并集
A0開頭，拼接上[A1,A2]的所有全排列
A1開頭，拼接上[A0,A2]的所有全排列
A2開頭，拼接上[A0,A1]的所有全排列
是以，對于[A0, A1, ……，An]的全排列，我們可以将問題轉換成n個子問題：
A0開頭，拼接上[A1,A2 ……，An]的所有全排列
A1開頭，拼接上[A0,A2 ……，An]的所有全排列
……
An開頭，拼接上[A0,A2 ……，A(n-1)]的所有全排列
而每個子問題又可以繼續向下轉化成n-1個子問題，最終可以轉化到隻有一個元素的全排列問題。
對于數組中有重複元素的情況，我們隻要保證，重複元素隻能有一次作為子問題的開頭元素，這樣我們就可以避免重複計算。
2. 基于枚舉方式（循環實作）
如果我們将全排列按照大小順序進行排序，假設我們知道了第i個排列是[A0, A1, A2, A3, ……]，那麼第i+1個排列就是比[A0, A1, A2, A3, ……]大，且最小的那個。找到i+1個排列的步驟如下
1）從後往前兩兩比較，找到第一個滿足a[i]<a[i+1]的兩個元素
2）從a[i+1]開始往後找，找到一個大于a[i]中最小的一個元素,這個元素的下标記為j，交換a[i]和a[j]
3）将[i+1, a.length-1]的元素全部逆序
3. 代碼實作
下面是java代碼的實作
package interviewquestion;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
public class Permutation {
//傳回 裝有回字元串s的全排列的List對象
public static List<String> byTraverse(String s){
char[] chArr = s.toCharArray();
List<String> list = new LinkedList<String>();
byTraverse0(chArr, 0, list);
return list;
}
private static void byTraverse0(char[] arr, int left, List<String> list){
if(left >= arr.length-1){
list.add(new String(arr));
return;
}
//用于記錄交換到left下标的每一個元素，防止計算重複的排列
HashSet<Character> hs = new HashSet<Character>();
for(int i = left; i < arr.length; i++){
//arr[left]後面的每一個元素arr[i]都和arr[left]交換
swap(arr, left, i);
if(!hs.contains(arr[left])){
hs.add(arr[left]);
byTraverse0(arr, left+1, list);
}
//将left和i交換回來，防止遺漏，重複
//已保證下一個交換到left下标的是未交換過的元素
swap(arr, left, i);
}
}
/*=================================================*/
//傳回 裝有大于等于字元串s的全排列的List對象
public static List<String> byNext(String s){
char[] arr = s.toCharArray();
List<String> list = new LinkedList<String>();
list.add(s);
while(next(arr)){
list.add(new String(arr));
}
return list;
}
private static boolean next(char[] arr){
boolean hasNext = false;
int i;
for(i = arr.length-2; i >= 0; i--){
if(arr[i] < arr[i+1]){
hasNext = true;
break;
}
}
//如果所有元素是從大到小排列，說明是最大的字元串
if(!hasNext){
return false;
}
//從i+1的下标往後找（必定是單調遞減）,找一個比arr[i]大的集合中最小的一個
int j;
for(j = i+1; j < arr.length; j++){
if(arr[j] <= arr[i]){
break;
}
}
j--;
//交換這兩個元素，然後逆序i+1以後的所有元素
swap(arr, i, j);
reverse(arr, i+1, arr.length-1);
return true;
}
private static void reverse(char[] arr, int from, int to){
for(int i = from, j = to; i < j; i++, j--){
swap(arr, i, j);
}
}
/*=================================================*/
private static void swap(char[] chArr, int i, int j){
char t = chArr[i];
chArr[i] = chArr[j];
chArr[j] = t;
}
public static void main(String[] args){
List<String> list1 = Permutation.byNext("1233");
System.out.println(list1);
System.out.println(list1.size());
System.out.println();
List<String> list2 = Permutation.byTraverse("1233");
System.out.println(list2);
System.out.println(list2.size());
}
}
運作結果
[1233, 1323, 1332, 2133, 2313, 2331, 3123, 3132, 3213, 3231, 3312, 3321]
12
[1233, 1323, 1332, 2133, 2313, 2331, 3213, 3231, 3123, 3132, 3312, 3321]
12