排列 与 全排列
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。
当m=n时所有的排列情况叫全排列。如果这组数有n个，那么全排列数为n!个。
对于全排列的求解可以使用递归，这里介绍几个方便的函数()，得到全排列。
对于序列{ 'a' , 'b' , 'c'}（之后为了方便，不打单引号，嘻嘻），每一个元素都比后面的小，按照字典序列，固定a之后，a比b，c都小，c比b大，它的下一个序列即为{a, c, b}，而{a, c, b}的上一个序列即为{a, b, c}，同理可以推出所有的六个序列为：{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a}，其中{a, b, c}没有上一个元素，{c, b, a}没有下一个元素。
头文件：#include <algorithm>
prev_permutation(start，end) “上一个排列组合”
函数模板：prev_permutation(arr, arr+size)说明：arr数组名，size数组元素个数返回值：bool型，当 当前序列 不存在上一个排列时，返回false，否则返回true，排列好的元素储存在数组中（所以想要看到全部的排列情况需要不断地输出数组里的元素）注意：在使用前需要对待使用的数组按照降序排列，否则只会输出该序列之后的排列情况。
next_permutation(start，end) “下一个排列组合”
函数模板：next_permutation(arr，arr+size)说明：arr数组名，size数组元素个数返回值：bool型，当 当前序列 不存在下一个排列时，返回false，否则返回true，排列好的元素储存在数组中（所以想要看到全部的排列情况需要不断地输出数组里的元素）注意：在使用前需要对待使用的数组按照升序排列，否则只会输出该序列之后的排列情况。
#include <iostream>#include <algorithm>using namespace std;int main (){int arr[] = {3,2,1};cout<<"用prev_permutation对3 2 1的全排列"<<endl;do{cout << arr[0] << ' ' << arr[1] << ' ' << arr[2]<<'\n';}while ( prev_permutation(arr,arr+3) );///获取上一个较大字典序排列，如果3改为2，只对前两个数全排列int arr1[] = {1,2,3};cout<<"用next_permutation对1 2 3的全排列"<<endl;do{cout << arr1[0] << ' ' << arr1[1] << ' ' << arr1[2] <<'\n';}while ( next_permutation(arr1,arr1+3) );///获取下一个较大字典序排列，如果3改为2，只对前两个数全排列///注意数组顺序，必要时要对数组先进行排序return 0;}
现学现用：
一、杭电1027Ignatius and the Princess II
http://acm./showproblem.php?pid=1027（注意while的条件）
对N个数进行全排列，从小到大，找到第M个全排列然后输出
运用上面的next_permutation函数，可以很快解决，但是在使用do-while循环的时候要注意括号里的条件
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int maxn = 1010;int a[maxn];void permutation(int n,int m){int count=0;do{count++;}while( count<m && next_permutation(a,a+n) );}int main (){int N,M;while(scanf("%d%d",&N,&M)!=EOF){for(int i=0;i<maxn;i++){a[i]=i+1;}permutation(N,M);for(int i=0;i<N;i++){if(i!=N-1)printf("%d ",a[i]);elseprintf("%d\n",a[i]);}}return 0;}
上面这幅图的判断条件是：
while( count<m && next_permutation(a,a+n) )
这个在进行条件判断时，是先判断count的值，再来调用next_permutation函数
使用下面这串代码也可以
void permutation(int n,int m){int count=0;do{count++;}while( next_permutation(a,a+n) && count<m-1 );}
上面这幅图的判断条件是：
while( next_permutation(a,a+n) && count<m-1 )
先count+1然后调用next_permutation函数。如给出的样例，6，4。当count到3的时候，在来进行判断时，判断条件有两个语句，所以是先执行next_permutation，再判断count，所以，count应小于m-1。
二、杭电1716 排序2
http://acm./showproblem.php?pid=1716
（我觉得掌握了上面的两个函数，那么1716的难点在于输出格式）
需要设置一个变量pre来记录下一个全排列的a[0]和之前的a[0]是否一样。
如果a[0]=0，则跳过
同一行中每个四位数间用空格分隔，每组输出数据间空一行
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int maxn = 1010;int a[maxn];int main (){int count,pre,t=0,flag;while(1){count=0;flag=0;for(int i=0;i<4;i++){scanf("%d",&a[i]);if(!a[i])++count;}if(count==4)return 0;if(t)printf("\n");t=1;flag=1;pre=a[0];do{if(a[0]==0)continue;if(flag){printf("%d%d%d%d",a[0],a[1],a[2],a[3]);flag=0;}else if(pre==a[0]){printf(" %d%d%d%d",a[0],a[1],a[2],a[3]);}else{printf("\n%d%d%d%d",a[0],a[1],a[2],a[3]);}pre=a[0];}while( next_permutation(a,a+4) );printf("\n");}return 0;}
三、杭电OJ 5055 Bob and math problem
http://acm./showproblem.php?pid=5055
该题是要在全排列中找到最大的奇数，所以和上面两题用的函数不一样，先让数组中的数字按照降序排列（从大到小），然后用prev_permutation(a,a+n)，加一些条件限制，注意换行，找到的第一个符合条件的，就是answer，然后break，退出循环，用一个flag变量标记，如果在循环里没有输出，则表明没有找到符合条件的数，那么在退出循环之后，输出-1
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int maxn = 105;int a[maxn];bool cmp(int a,int b){return a>b;}int main (){int n,i,flag;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n,cmp);flag=0;do{if(a[n-1]%2==1 && a[0]!=0){for(i=0;i<n;i++){printf("%d",a[i]);}printf("\n");flag=1;break;}}while( prev_permutation(a,a+n) );if(!flag){printf("-1\n");}}return 0;}
方法二解5055/CSDN___CSDN/article/details/84893748
四、POJ 1146 ID Codes
本题关键在于读懂题意，要求输出的是下一个全排列，如果下一个全排列不存在，则输出No Successor
/problem?id=1146
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 1000000;char str[maxn];int main (){int len;while(scanf("%s",str)!=EOF){if(strcmp(str,"#")==0)return 0;len=strlen(str);if(next_permutation(str,str+len))printf("%s\n",str);elseprintf("No Successor\n");}return 0;}
五、POJ 3187Backward Digit Sums
/problem?id=3187
就通过前面几个得到规律，按照这种倒三角的加法
一个数：1 -----> 1*a[0]
两个数：1 1 -------> 1*a[0]+1*a[1]
三个数：1 2 1 --------> 1*a[0]+2*a[1]+1*a[2]
四个数：1 3 3 1 ----------->1*a[0]+3*a[1]+3*a[2]+1*a[3]
是杨辉三角，所以先储存杨辉三角，再用next_permutation函数，我就是手动推倒了几个，大佬应该一眼就看出来了吧，
嘻嘻嘻，我是呆瓜
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int a[12],k[12][12];void fun(){int i,j;for(i=1;i<=10;i++){for(j=1;j<=i;j++){if(i==1 || j==i || j==1)k[i][j]=1;elsek[i][j]=k[i-1][j]+k[i-1][j-1];}}}int main (){int i,j,N,M,sum;fun();while(scanf("%d%d",&N,&M)!=EOF){for(i=0;i<N;i++){a[i]=i+1;}do{sum=0;for(i=0,j=1;i<N,j<=N;i++,j++)sum+=(a[i]*k[N][j]);if(sum==M)break;}while(next_permutation(a,a+N));for(i=0;i<N;i++)printf("%d ",a[i]);printf("\n");}return 0;}
之后会推出用递归的方法求解全排列，
还有，如果在遇到全排列的题会做相应的补充
有错的话，希望读者及时指正
