字元串全排列-遞歸實作

一個算法命題：給定字元串S[0…N-1]，設計算法，枚舉S的全排列。如：123，全排列就是：123,132,213,231,312,321

算法思考

根據遞歸的特點，深度劃分子邏輯-遞歸，辨別出口。全排列一個思維：對待全排序的序列中從左標明一個數作為基數，然後對他右邊的數進行全排列，以此遞歸。

算法描述

以字元串1234為例：

1 – 234

2 – 134

3 – 214

4 – 231

如何保證不遺漏： 每次遞歸前，保證1234的順序不變。

算法演進

如1234序列，其中from和to指的是待全排序序列的首位置和尾位置。位置參考的是原序列長度

第一次就是from 0 to 3的全排列，標明1為基數，逐一的與後面序列每個數交換就得到以它為首的全部全排序序列，234就是進行 子全排列；然後在子全排列序列中就是from 1 to 3的全排列，標明2作為基數，34就是繼續進行的 子全排列；然後在34中就是from 2 to 3的全排列，標明3為基數，4就是繼續進行的 子全排列；...這時遞歸的深度會變大

當from == to相等時，自然不需要交換，全排序序列隻有一個就是他自己，此時列印就好，此時return，遞歸就會往回走，然後根據循環走其他分支遞歸，直到沒有分支遞歸，本層遞歸結束繼續向上走。

如圖：

java代碼實作

不考慮有重複字元序列：

public static void Permutation(char[] s, int from, int to) {
        if(to<=1)
            return;
        if(from == to){
            System.out.println(s);
        }
        else{
           for(int i=from;i<=to;i++){
        	   
        	swap(s,i,from);
        	Permutation(s,from+1,to);
        	swap(s,from,i);
            }
        }
    }
    
    
    public static void swap(char[] s, int i, int j) {
    	char temp = s[i];
    	s[i] = s[j];
    	s[j] = temp;
    }
  public static void main(String[] args) {
     StrRemove s1 = new StrRemove();
     String waitList1 = "1234";
     String waitList2 = "1223";
     Permutation(waitList1.toCharArray(), 0, waitList1.length() - 1);
  }
           

測試1234：

1234
1243
1324
1342
1432
1423
2134
2143
2314
2341
2431
2413
3214
3241
3124
3142
3412
3421
4231
4213
4321
4312
4132
4123
           

有重複的字元序列該如何保證不重複？如1223序列？

解決：帶重複字元的全排列就是每個字元分别與它後面非重複出現的字元交換。

代碼：

public static void main(String[] args) {
		String waitList1 = "1234";
		Permutation(waitList1.toCharArray(), 0, waitList1.length() - 1);
	}
	
    public static void Permutation(char[] s, int from, int to) {
        if(to<=1)
            return;
        if(from == to){
            System.out.println(s);
        }
        else{
           a:for(int i=from;i<=to;i++){
        	 //排除重複：帶重複字元的全排列就是每個字元分别與它後面非重複出現的字元交換
        	 for(int j=from;j<i;j++){
	           if(s[j] == s[i]){
	           	continue a;
	           }
        	}
        	   
        	swap(s,i,from);
        	Permutation(s,from+1,to);
        	swap(s,from,i);
            }
        }
    }
    
    
    public static void swap(char[] s, int i, int j) {
    	char temp = s[i];
    	s[i] = s[j];
    	s[j] = temp;
    }
           

測試：

1224
1242
1422
2124
2142
2214
2241
2421
2412
4221
4212
4122
           

算法複雜度分析

重複字元的全排列遞歸算法時間複雜度：

 ∵f(n) = n*f(n-1) + n^2

∵f (n-1)=(n-1)*f(n-2) + (n-1)^2

 ∴f(n) = n*((n-1)*f(n-2) + (n-1)^2) + n^2

 ∵ f(n-2) = (n-2)*f(n-3) + (n-2)^2

 ∴ f(n) = n*(n-1)*((n-2)*f(n-3) + (n-2)^2) + n*(n-1)^2 + n^2

 = n*(n-1)*(n-2)*f(n-3) + n*(n-1)*(n-2)^2 + n*(n-1)^2 + n^2

 =.......

 < n! + n! + n! + n! + ... + n!

 = (n+1)*n!

 時間複雜度為O((n+1)!)

 注：當n足夠大時：n! > n+1

字元串全排列-非遞歸實作