【面试题25】字符串的排列

题目：输入一个字符串，打印出该字符串中字符的所有排列。

例如输入字符串abc，则打印由字符a,b,c所能排列出来的所有字符串：abc，abc,bac,bca,cab,cba

我们求整个字符串的排列，可以看成两步：首先求出所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。下图就是分别把第一个字符a和后面的b,c交换的情景。第二步固定第一个字符，求后面所有字符的排列。这个时候我们仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换……

注：（a)把字符串分为两部分，一部分是字符串的第一个字符，另一部分是第一个字符以后的所有字符。接下来我们求阴影部分的字符串的排列。（b）拿第一个字符和它后面的字符逐个交换。

1. public class E28StringPermutation {  
2.       
3.     public void swap(char[] arr,int idx1,int idx2){  
4.         char temp = arr[idx1];  
5.         arr[idx1] = arr[idx2];  
6.         arr[idx2] = temp;  
7.     }  
8.     public void permutation(char[] arr,int index,int size){  
9.         if(index == size){  
10.             for(int i = 0;i<arr.length;i++){  
11.                 System.out.print(arr[i]+ " ");  
12.             }  
13.             System.out.println();  
14.         }  
15.         else{  
16.             for(int i = index;i<size;i++){  
17.                 if(i!=index && arr[i] == arr[index])  
18.                     continue;  
19.                 swap(arr,i,index);  
20.                 permutation(arr,index+1,size);  
21.                 swap(arr,i,index);  
22.             }  
23.         }  
24.     }  
25.     public static void main(String[] args){  
26.         String str="abcd";  
27.         char[] chs = str.toCharArray();  
28.         E28StringPermutation test = new E28StringPermutation();  
29.         test.permutation(chs,0,4);  
30.     }  
31. }