全排列

1. 递归实现全排列；

• 首先来说递归算法实现全排列： 例如，对于{1,2,3,4}的例子进行全排列，其可以分解成 每个首字母 +剩余字母全排列， 因此，我们可以使用递归的形式进行编写；

我们按照每个首字母+剩余字母全排列 来 编写递归的主体，递归的主体可以写成：

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);
        }
    }
 }

2. 有重复数字的全排列
   有重复数字时，使用上述递归算法进行全排列会产生重复的结果，此时，需要对该算法进行微调（需要找到一个剪枝的条件，上述递归算算法实际上为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;
    }

3. 字典序实现全排列
   字典序可以控制全排列的顺序，例如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位置往后的所有元素进行逆序排列；

image.png