算法-求全排列

题目:数字1,2,3,4全排列。

全排列

思路:使用递归策略将待排数列逐一缩小。例如1,2,3,4。先把1固定,递归求2,3,4的全排列;又把2固定,递归求3,4全排列……直到只剩一个数,输出这个排列。图解如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
   private static void permutation(int[] array, int index) {
if (index == array.length - 1)
System.out.println(Arrays.toString(array));

//从固定的数,与后面每一位交换
for (int i = index; i < array.length; i++) {
swap(array, i, index);
permutation(array, index + 1);//确定第index位的数值
swap(array, i, index);
}
}

private static void swap(int[] array, int i, int index) {
int temp=array[i];
array[i]=array[index];
array[index]=temp;
}

带重复值的全排列

例如:1,2,3,2

当进行到index=0时,固定{1}+P(2,3,2),接下来求子串(2,3,2)的全排列,但其中有两个2,无论哪个与此时的1交换,后面的子串都相同,会重复。故需要跳过保留其中一种就可以了,查询是否重复的区间为当前进行到的位置index和准备交换的位置i,在i之前若有重复的,则说明index位置元素不需要再与i位置交换计算了。代码如下:

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
private static void permutation(int[] array, int index) {
if (index == array.length - 1)
System.out.println(Arrays.toString(array));

// 用当前位值,与后面每一位交换
for (int i = index; i < array.length; i++) {
if(check(array,index,i)){
swap(array, i, index);
permutation(array, index + 1);//确定第index位的数值
swap(array, i, index);
}
}
}

private static boolean check(int[] array, int index, int i) {
if (i > index) {//兼容index=i的情况
for (int j = index; j < i; j++) {
if (array[j] == array[i])
return false;
}
}
return true;
}

private static void swap(int[] array, int i, int index) {
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
Donate comment here