全排列

生成1～n的排列

       我们尝试用递归的思想解决：先输出所有以1开头的排列（这一步是递归调用），然后 输出以2开头的排列（又是递归调用），接着是以3开头的排列……最后才是以n开头的排 列。
        以1开头的排列的特点是：第一位是1，后面是2～9的排列。根据字典序的定义，这些2 ～9的排列也必须按照字典序排列。换句话说，需要“按照字典序输出2～9的排列”，不过需 注意的是，在输出时，每个排列的最前面要加上“1”。这样一来，所设计的递归函数需要以 下参数：
已经确定的“前缀”序列，以便输出。 需要进行全排列的元素集合，以便依次选做第一个元素。
这样可得到一个伪代码：

void print_permutation(序列A, 集合S)
{
    if(S为空) 输出序列A;
     else 按照从小到大的顺序依次考虑S的每个元素v
      {
       print_permutation(在A的末尾填加v后得到的新序列, S-{v});
   }
}      

       暂时不用考虑序列A和集合S如何表示，首先理解一下上面的伪代码。递归边界是S为空 的情形，这很好理解：现在序列A就是一个完整的排列，直接输出即可。接下来按照从小到大的顺序考虑S中的每个元素，每次递归调用以A开头。

        下面考虑程序实现。不难想到用数组表示序列A，而集合S根本不用保存，因为它可以 由序列A完全确定——A中没有出现的元素都可以选。C语言中的函数在接受数组参数时无法 得知数组的元素个数，所以需要传一个已经填好的位置个数，或者当前需要确定的元素位置 cur，代码如下：

#include<iostream>
using namespace std;
const int maxn=10000;
int a[maxn];
void print_permutation(int n,int a[],int cur)
{
    if(cur==n)     //递归边界 
    {
        for(int i=0;i<n;i++) cout<<a[i];
        cout<<endl;
    }
    else
    {
        for(int i=1;i<=n;i++)   //尝试a[cur]中从小到大填1-n各个整数 
        {
            int ok=1;    //标志元素i是否已经用过 
            for(int j=0;j<cur;j++)
            if(a[j]==i) ok=0;  //i已经用过，ok标记为0 
            if(ok)
            {
                a[cur]=i;   //i未用过，把它添加到序列末尾后继续递归调用 
                print_permutation(n,a,cur+1);
            }
        }
    }
}
int main()
{
    int n;
    cin>>n;
    print_permutation(n,a,0);
    return 0;
}

     循环变量i是当前考察的A[cur]。为了检查元素i是否已经用过，上面的程序用到了一个 标志变量ok，初始值为1（真），如果发现有某个A[j]==i时，则改为0（假）。如果最终ok仍 为1，则说明i没有在序列中出现过，把它添加到序列末尾（A[cur]=i）后递归调用。
     声明一个足够大的数组A，然后调用print_permutation(n, A, 0)，即可按字典序输出1～n的 所有排列。

 给定数组的全排列

       如果把问题改成：输入数组P，并按字典序输出数组A各元素的所有全排列，则需要对 上述程序进行修改——把P加到print_permutation的参数列表中，然后把代码中的if(A[j] == i) 和A[cur] = i分别改成if(A[j] == P[i])和A[cur] = P[i]。这样，只要把P的所有元素按从小到大的
顺序排序，然后调用print_permutation(n,  A, 0，p)即可。（注意：此方法数组内元素不可重复）

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10000;
int a[maxn];
void print_permutation(int n,int a[],int cur,int p[])
{
    if(cur==n)     //递归边界 
    {
        for(int i=0;i<n;i++) cout<<a[i];
        cout<<endl;
    }
    else
    {
        for(int i=0;i<n;i++)   //尝试a[cur]中从小到大填p[i]中的各个整数 
        {
            int ok=1;    //标志元素i是否已经用过 
            for(int j=0;j<cur;j++)
            if(a[j]==p[i]) ok=0;  //p[i]已经用过，ok标记为0 
            if(ok)
            {
                a[cur]=p[i];   //p[i]未用过，把它添加到序列末尾后继续递归调用 
                print_permutation(n,a,cur+1,p);
            }
        }
    }
}
int main()
{
    int p[20];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>p[i];
    sort(p,p+n);
    print_permutation(n,a,0,p);
    return 0;
}

生成可重集的排列

方法一：

      一个解决方法是统计A[0]～A[cur-1]中P[i]的出现次数c1，以及P数组中P[i]的出现次数 c2。只要c1<c2，就能递归调用。结果又如何呢？输入1 1 1，输出了27个1 1 1。遗漏没有了，但是出现了重复：先试着把 第1个1作为开头，递归调用结束后再尝试用第2个1作为开头，递归调用结束后再尝试用第3 个1作为开头，再一次递归调用。可实际上这3个1是相同的，应只递归1次，而不是3次。
       换句话说，我们枚举的下标i应不重复、不遗漏地取遍所有P[i]值。由于P数组已经排过 序，所以只需检查P的第一个元素和所有“与前一个元素不相同”的元素，即只需在“for(i = 0; i < n; i++)”和其后的花括号之前加上“if(!i || P[i] != P[i-1])”即可。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10000;
int a[maxn];
void print_permutation(int n,int a[],int cur,int p[])
{
    if(cur==n)     //递归边界 
    {
        for(int i=0;i<n;i++) cout<<a[i];
        cout<<endl;
    }
    else
    {
        for(int i=0;i<n;i++)   //尝试a[cur]中从小到大填p[i]中的各个整数 
        {
            if(p[i]!=p[i-1])
            {
            int c1=0,c2=0;
            for(int j=0;j<cur;j++) if(a[j]==p[i]) c1++;
            for(int j=0;j<n;j++)   if(p[j]==p[i]) c2++;
            if(c1<c2)
            {
                a[cur]=p[i];
                print_permutation(n,a,cur+1,p);
            }
        }
        }
    }
}
int main()
{
    int p[20];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>p[i];
    sort(p,p+n);
    print_permutation(n,a,0,p);
    return 0;
}

 方法二：

      枚举所有排列的另一个方法是从字典序最小排列开始，不停调用“求下一个排列”的过 程。如何求下一个排列呢？C++的STL中提供了一个库函数next_permutation。看看下面的代 码片段，就会明白如何使用它了。

#include<cstdio>
#include<algorithm>
using namespace std;
int main( ) {
    int n, p[10];
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &p[i]);
    sort(p, p+n);      //排序，得到p的最小排列 
    do {
        for(int i = 0; i < n; i++) printf("%d ", p[i]);
        printf("
");
    } while(next_permutation(p, p+n)); 
    return 0;
}
    
    

需要注意的是，上述代码同样适用于可重集。