字符串的全排列

题目

　　输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

分析

　　用递归的思想。将第一个字符与后面的交换位置；然后固定第一个字符，求后面所有字符的排列.......

代码

 1     public ArrayList<String> list = new ArrayList<String>();
 2     
 3     public ArrayList<String> Permutation(String str){
 4         if(str.length()==0)
 5             return list;
 6         char[] c = str.toCharArray();
 7         Per(c, 0, str.length()-1);
 8         
 9         return list;
10     }
11     
12     public void Per(char[] c, int low, int high){
13         if(low>high){
14             String s = new String(c);
15             list.add(s);
16             Collections.sort(list);
17             
18         }
19         else{
20             for(int i=low;i<=high;i++){
21                 if(i==low || c[i]!=c[low]){
22                     char temp = c[low];
23                     c[low] = c[i];
24                     c[i] = temp;
25                     
26                     Per(c, low+1, high);
27                     
28                     temp = c[low];
29                     c[low] = c[i];
30                     c[i] = temp;
31                 }
32             }
33         }    
34     }