全排列递归算法(元素有重复与无重复，C++实现)

元素无重复：

　　如：2,5,8,9.

　　思路：用递归的方法解决，对于2589，先输出所有以2开头的排列，然后输出5开头的排列.....（此处称为递归操作A）。以2开头的排列中，第一位是2，后面的是589，然后对589执行相同的递归操作A......

　　代码如下：

　　

#include<iostream>
using namespace std;
void print_permutation(int n,int *A,int *B,int cur){//n为目标数组长度，cur为对全排列序列A递归操作的下标 
    if(cur==n){//递归出口 
        for(int i=0;i<n;i++)//打印全排列序列 
            cout<<A[i]<<" ";
            cout<<endl;
    }
    else 
    for(int i=0;i<n;i++){//扫描目标数组 
        int ok=1;
        for(int j=0;j<cur;j++){
            if(A[j]==B[i]){
                ok=0;//对A中已有元素（cur下标前的元素）进行扫描，若发现A中已经存在B[i]的值时，说明B[i]元素已经排列过。 
                break; 
            } 
        }
        if(ok){//若B[i]未排列过，则将B[i]添加到A序列末尾，将cur指针后移一位，进行下一步递归操作。 
            A[cur]=B[i];
            print_permutation(n,A,B,cur+1);
        }
    }     
} 

int main(){
    int a[]={0};//全排列序列，即输出结果 
    int b[]={2,5,8,9};// 目标数组 
    print_permutation(4,a,b,0);
    return 0;
}

元素有重复：

　　修改两个地方：

　　1.因为元素可以重复，所以不能再用“A中是否已经存在B数组”的条件来决定是否添加B[i]元素。取而代之，分别对A，B数组扫描，只要A中的B[i]不超过B中的B[i]即可。

　　2.在题目要求上，重复元素属于相同元素时，如1123的排列中1123和1123是等价的，只能算一种。我们最好先对B数组排个序（排序复杂度是nlogn，相较于两层循环的代，影响并不是很大)，然后在最外层循环添上一个控制条件(i==0||B[i]!=B[i-1]),为的就是防止重复的元素又一次排列。

　　代码如下：

　　

#include<iostream>
using namespace std;
void print_permutation(int n,int *A,int *B,int cur) {
    if(cur==n) {
        for(int i=0; i<n; i++)
            cout<<A[i]<<" ";
        cout<<endl;
    } else
        for(int i=0; i<n; i++) {
            if(!i||B[i]!=B[i-1]) {
                int c1=0,c2=0;
                for(int j=0; j<cur; j++)//扫描A中已有B[i]的个数 
                    if(A[j]==B[i]) c1++;
                for(int j=0; j<n; j++)//扫描B中所有B[i]的个数 
                    if(B[j]==B[i]) c2++;
                if(c1<c2) {
                    A[cur]=B[i];
                    print_permutation(n,A,B,cur+1);
                }
            }
        }
}

int main() {
    int a[]= {0};
    int b[]= {1,1,2,4};
    print_permutation(4,a,b,0);
    return 0;
}