排列  与  全排列

从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;
}

现学现用：

一、杭电1027  Ignatius and the Princess II

http://acm.hdu.edu.cn/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.hdu.edu.cn/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.hdu.edu.cn/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 https://blog.csdn.net/CSDN___CSDN/article/details/84893748

四、POJ 1146  ID Codes

本题关键在于读懂题意，要求输出的是下一个全排列，如果下一个全排列不存在，则输出No Successor

http://poj.org/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 3187 Backward Digit Sums

http://poj.org/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;
}

之后会推出用递归的方法求解全排列，

还有，如果在遇到全排列的题会做相应的补充

有错的话，希望读者及时指正