字符串全排列-递归实现

一个算法命题：给定字符串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

字符串全排列-非递归实现