题目

给三个字符,例如abc,取得他的全排列abc, acb, bca, dac, cab, cba

解答

1. 递归和容器实现全排列

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
public class Allrange {
ArrayList<String> bucket = new ArrayList<String>();
public static void main(String[] args) {
String str = "123";
new Allrange().range(str);
}

void swap(char[] chars, int a, int b) {
char temp = chars[a];
chars[a] = chars[b];
chars[b] = temp;
}

void range(String str) {
int strLength = str.length();
char[] chars = str.toCharArray();
for (int i = 0; i < strLength; i++) {
if (i == strLength - 1) {//如果是最后一个字符的时候,和第一个替换
swap(chars, i, 0);
} else {
swap(chars, i, i + 1);//和后一个字符替换
}
String result = String.valueOf(chars);
if(!bucket.contains(result)){
Log.d(result);
bucket.add(result);
range(result);//输出里含有这个字符就继续排列,直到输出里面没有
}

}

}
}

输出

1
2
3
4
5
6
213
123
231
321
312
132

算法复杂度分析

流程

1
2
3
4
5
6
7
8
9
10
11
                        123  
213 231
312

312 X
123 132 123 X
231 X

231 X
321 312 X
123 X

第一级递归把结果放到容器,第二级递归使用了ArrayList的contains方法判断是否在容器内,不在容器内的就继续递归。