枚举排列的两种方法：递归枚举 和 next_permutation()函数

照着《入门经典》理解整理了一下。

① 以字典序生成1~n的排列 （递归枚举）

运用一层层的递归，形成一个解答树。

#include<cstdio>
using namespace std;
void print_permutation_1(int n,int *ar,int cur)
{
                       //ar存储排列，cur表示当前ar中排列到第几个if(cur==n)      //当cur==n，即已排列到末尾，则打印该排列{
    for(int i=0; i<n; i++)printf("%d ",ar[i]);printf("\n");}else{
    for(int i=1; i<=n; i++)        //从1~n选择元素放入当前的ar[cur]{
    bool ok=true;for(int j=0; j<cur; j++ )  //确保选择的i还不在排列中{
    if(ar[j]==i)ok=false;}if(ok){
    ar[cur]=i;print_permutation_1(n,ar,cur+1);   //递归，cur+1}}}
}

② 以字典序生成可重集的排列 （递归枚举）
给定一个数组P，按字典序输出所有排列，数组P中会有重复元素。

要先让数组P从小到大排好序，答案不能有重复的排列，也不能缺少元素。

#include<cstdio>
using namespace std;
void print_permutation_2(int n,int *P, int *ar,int cur)
{
    if(cur==n){
    for(int i=0; i<n; i++)printf("%d ",ar[i]);printf("\n");}else{
    for(int i=0; i<n; i++)      //从P[0]到P[n-1]选择元素放入当前ar[cur]{
    //因为之后要通过比较P和ar中该元素的数量来判断是否选择该元素，//所以用以下的if来略过相同元素，以此防止出现相同排列。if(i==0||(i!=0&&P[i]!=P[i-1])) {
    int c1=0,c2=0;             //c1记录ar中该元素的数量for(int j=0; j<cur; j++ )  //c2记录P中该元素的数量{
    if(ar[j]==P[i])c1++;}for(int j=0; j<n; j++){
    if(P[j]==P[i])c2++;}if(c1<c2) {
    ar[cur]=P[i];print_permutation_2(n,P,ar,cur+1);   //递归，cur+1}}}}
}

③使用C++ STL中的全排列函数next_permutation

对于next_permutation函数，其函数原型为：

 #include <algorithm>bool next_permutation(iterator start,iterator end)

若当前序列不存在下一个排列时，函数返回false，否则返回true

给next_permutation()函数提供一个原排列，就可以得到该排列的下一个排列（字典序）并返回true，到了该排列字典序的最后一个排列则返回false。

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);        //生成最小的排列do{
    for(int i=0;i<n;i++)printf("%d ",P[i]);printf("\n");}while(next_permutation(P,P+n));  //从 首地址 到 末地址+1return 0;
}