全排列
- 递归实现全排列;
- 首先来说递归算法实现全排列: 例如,对于{1,2,3,4}的例子进行全排列,其可以分解成 每个首字母 +剩余字母全排列, 因此,我们可以使用递归的形式进行编写;
首字母 | 剩余字母全排列 |
---|---|
1 | 2,3,4; 3,2,4... |
2 | 1,3,4; 1,4,3... |
3 | 1,2,4; 1,4,2... |
4 | 1,2,3; 1,3,2... |
我们按照每个首字母+剩余字母全排列 来 编写递归的主体,递归的主体可以写成:
for(int i=0;i<length;i++){
swap(A,0,i); //将数组A的每个字母调换到首位;
perm(A,1,length);//对除首位的部分,递归调用全排列;
swap(A,0,i); //注意:将数组还原,为下次调换做准备,否则难以保证将每个字母都调换到了首位;
}
我们加上结束条件(当只有一个数字进行全排列时),完整的程序如下:
public void permute( List list,int[] A, int p,int q){
if(p==q){
list.add(A.clone());
}
else{
for(int i=p;i<q;i++){
swap(A,p,i);
permute(list,A,p+1,q);
swap(A,p,i);
}
}
}
-
有重复数字的全排列
有重复数字时,使用上述递归算法进行全排列会产生重复的结果,此时,需要对该算法进行微调(需要找到一个剪枝的条件,上述递归算算法实际上为DFS);
举例:1,1,2,3,4,3进行全排列运算,按照上述的递归逻辑, 可拆成以下状态:
此时,我们可以看到红色框和黄色框中的数字各自是相同的(不考虑顺序),因此,这些数字组成的所有全排列也肯定是相同的,这是该递归算法存在的问题。
在此,在与首数字进行调换时,我们判断该数字之后是否还存在该数字,如果否,才进行调换:
例如,在进行遍历时,红色的3不换到首位,只有绿色的3才会换到首位,以避免上述重复现象出现;
代码调整如下:
public void permute( List list,int[] A, int p,int q){
if(p==q){
list.add(A.clone());
}
else{
for(int i=p;i<q;i++){
if(!swapAccepted(A,p,i)) continue; //判断是否后面还有重复数字(即相同的数字,只有位于最后的数字才会换到首位)
swap(A,p,i);
permute(list,A,p+1,q);
swap(A,p,i);
}
}
}
/**
剪枝条件
**/
public static boolean swapAccepted(int[] array, int start, int end) {
for (int i = start; i < end; i++) {
if (array[i] == array[end]) {
return false;
}
}
return true;
}
-
字典序实现全排列
字典序可以控制全排列的顺序,例如1,2,3,4的字典序最后一个4,3,2,1。通过字典序,可以产生有大小顺序的全排列,字典序完成1,2,3,4到4,3,2,1的所有排列;
字典序的算法描述如下:
a. 从右向左,找出第一破坏递增顺序的元素,记其位置为i;
b. 从右向左,找出第一个大于A[i]的元素,及其位置为j;
c. 交换A[i]与A[j]两个元素;
d. 从i位置往后的所有元素进行逆序排列;