编程练习
题目：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路：仔细读题，发现可分解为两步：
1.对输入字符串做全排列；
2.将排列后的字符串做字典排序。
全排列可以采用最常用的方法：比如“abcd”,先交换a和后面的每个字符，即可得到“bacd”,”cbad”,”dbca”。然后固定第一个字符，对剩下的字符做相同的遍历，即递归：比如对于”bacd”来说，固定b，然后交换a和a之后的字符，即可得到”bcad”和”bdca”，然后再递归，交换后边的子字符串。
此外还需考虑特殊情况，比如”aabc”,”aa”,这种情况可能产生重复的字符串，需要对返回的结果做删除重复的字符串处理。
心路历程：困扰了我两天的难题，终于在今天解决了，一开始看错题目，以为是在排列中也需要用字典序排列，结果写错了代码，输出结果错误后来才发现是要写一个全排列出来，然后再对结果集做字典排序。字典排序可以调用ArrayList中的sort方法轻松实现，所以此题的重点在于全排列。
之前没有接触过全排列的算法，自己一开始用两层的嵌套for循环发现只能解决三个字符的问题，比如输入”abc”，但是如果输入”aabc”，两层嵌套for循环就远远不够用了，发现全排列应该要用递归解决，但是自己很难写出来，在网上查阅资料后发现了这个交换字符顺序，并在每个子字符串里递归调用的方法。自己写的时候一开始借助了很多辅助的list来维持或者记录某些不想让它改变的值，后来在一天午睡后突然灵光一现，既然不想让每次循环交换顺序的第一个元素发生改变，那在每次交换得到到字符串，将该字符串放入结果集list后，再按相同的顺序交换回去不就完了？这样瞬间解决了一个看似很无解的问题，说明只要用心想，总会有办法的。
此外，在写交换值的swap函数时，发现了不能直接交换，比如:
1 | public void swap(int a,int b){ |
这样的代码是行不通的，因为java的函数参数是值传递，它传进来的a，b是a,b的值，不是a,b本身的引用，所以在函数块内虽然a,b的值交换了，但是一出函数体，函数体外调用该函数的a,b仍然不变。所以需要借助引用类型的数据，比如数组，来实现引用的传递，借此真正改变函数体外的a,b的值。
代码如下：1
2
3
4
5public void swap(int [] arr,int a,int b){
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
java代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Permutation2 {
public static ArrayList<String> Permutation(String str) {
ArrayList<String> list=new ArrayList<String>();
if(str==null) {
return null;
}
//将str转为字符数组再将字符数组转为arraylist方便后续操作
char [] arr=str.toCharArray();
ArrayList<Character> charlist=new ArrayList<Character>();
for(Character c:arr) {
charlist.add(c);
}
//得到所有排列序列
pailie(list,charlist,0);
//删除重复的序列
ArrayList<String> flist=new ArrayList<String>();
for(int i=0;i<list.size();i++) {
str=list.get(i);
flist.add(str);
List<String> sublist = list.subList(i+1, list.size());
while(sublist.contains(str)) {
sublist.remove(str);
}
}
flist.sort(null);
return flist;
}
/**
* 格式化字符串
* @param pStr
*/
public static String formatStr(String pStr) {
pStr=pStr.replace("]", "");
pStr=pStr.replace("[", "");
pStr=pStr.replace(",", "");
pStr=pStr.replace(" ", "");
return pStr;
}
/**
* swap函数
* @param charlist1
* @param i
* @param j
*/
public static void swap(List<Character> charlist1,int i,int j) {
Character temp=charlist1.get(i);
charlist1.set(i, charlist1.get(j));
charlist1.set(j, temp);
}
/**
* 全排列函数
* @param list
* @param charlist
* @param start
*/
public static void pailie(ArrayList<String> list,List<Character> charlist,int start) {
if(charlist==null) {
return;
}
//先交换，交换后还得换回来，以保证下一次交换时start处位置的字符是第一次交换时的字符
for(int i=start;i<charlist.size();i++) {
swap(charlist,start,i);
String tmstr=charlist.toString();
tmstr=formatStr(tmstr);
list.add(tmstr);
pailie(list,charlist,start+1);
swap(charlist,start,i);
}
}
public static void main(String[] args) {
String s="aabc";
System.out.println(Permutation(s));
}
}