题目描述
给出一个具有重复数字的列表，找出列表所有不同的排列。
思路
参考不带重复元素的全排列，讨论那四种方法是否适合带重复元素的全排列。
穷举法
因为包含重复元素，穷举法显然不合适。
交换法
对于不带重复元素的全排列，交换法是最合适的。但如果包含重复元素，交换的过程中会出现许多重复元素之间的交换，这种交换显然是错误的，所以交换法不合适。
逆序阶乘进制法
直接不能用！因为对于包含重复元素的n个元素的数组，其全排列不会有n!种情况。
其实，只有后继法最合适！
后继法
后继法首先将数组按照升序排列，之后找当前数的下一个后继，每种后继都对应一种排列。直到最后找不到后继，完成全排列。
当出现重复元素时，不但不会影响原先的求后继数算法，而且还会减少求后继数的次数（因为有重复元素），所以后继法本身就最合适于带重复元素的全排列！
个人认为，不带重复元素的全排列，最适合用逆序阶乘进制法，交换法因为用递归所以稍逊
代码
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
| private List<List<Integer>> listHolder;
public List<List<Integer>> permuteUnique(int[] nums) {
listHolder = new ArrayList<List<Integer>>();
if(nums.length == 0) {
listHolder.add(new ArrayList<Integer>());
return listHolder;
}
Arrays.sort(nums);
addToListHolder(nums);
myPermuteUnique(nums);
return listHolder;
}
private void addToListHolder(int[] nums) {
Integer[] integers = new Integer[nums.length];
for(int i = 0; i < nums.length; i++) {
integers[i] = nums[i];
}
listHolder.add(new ArrayList<Integer>(Arrays.asList(integers)));
}
private void myPermuteUnique(int[] nums) {
int maxIndex;
int switchIndex;
// 如果存在极大值，寻找排列
while((maxIndex = getMaxIndex(nums)) != -1) {
int beforeMax = nums[maxIndex-1];
switchIndex = maxIndex;
// 寻找可交换元素下标
for(int i = maxIndex+1; i < nums.length; i++) {
if(nums[i] > beforeMax) {
switchIndex = i;
}else {
break;
}
}
// 交换元素
swap(maxIndex-1, switchIndex, nums);
// 从MaxIndex开始是降序排列，需要倒序得到后继数
int i = maxIndex;
int j = nums.length-1;
while(i < j) {
swap(i, j, nums);
i++;
j--;
}
// 找到一种排列，添加到List
addToListHolder(nums);
}
// 不存在MAX时，表示找到了所有排序
}
private void swap(int i, int j, int[] nums) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private int getMaxIndex(int[] nums) {
int i = nums.length-1;
while(i > 0) {
if(nums[i] > nums[i-1]) {
return i;
}
i--;
}
return -1;
}
|
考差点