全排列

递归实现全排列；

首先来说递归算法实现全排列：例如，对于{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;
    }