参考
问题
考虑三个字符所组成的序列{a,b,c}。
这个序列有六个可能的排列组合:abc,acb,bac,bca,cab,cba。而在这里我们是按照字典排序的。
对于这种排列组合问题我们一般常采用的是暴力枚举的方法,即dfs+回溯。但是殊不知,其实在头文件algorithm.h中给我们提供了一个非常强大且好用的全排列函数:
next_permutation()
全排列函数的使用
这里介绍两个计算序列全排列的函数:
next_permutation(start,end)
和
prev_permutation(start,end)
。这两个函数作用是一样的,区别就在于前者求的是当前排列的下一个排列,后一个求的是当前排列的上一个排列。至于这里的“前一个”和“后一个”,我们可以把它理解为序列的字典序的前后,严格来讲,就是对于当前序列pn,他的下一个序列pn+1满足:不存在另外的序列pm,使pn<pm<pn+1。
我们直接在代码示例中来看:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int num[3]={1,2,3};
do
{
cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
}while(next_permutation(num,num+3));
return 0;
}
这里我们使用
next_permutation(num,num+3)
对num数组中的3个数进行全排列。,这里面的num和num+3是需要全排列的序列的起始地址和结束地址。用法很简单,但是有一些小细节需要我们注意。
如果我们将
next_permutation(num,num+3)
改为
next_permutation(num,num+2),
运行结果如下图:
我们可以看到,全排序函数只对num数组中的前两个进行排列了,而第三个即num[2]依然在其所在位置没变。
另外,需要强调的是,next_permutation()在使用前需要对欲排列数组按升序排序,否则只能找出该序列之后的全排列数。比如,如果数组num初始化为2,3,1,那么输出就变为了:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int num[3] = { 2,3,1 };
do
{
cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
}while(next_permutation(num,num+2));
return 0;
}
{2,3,1}的结果:
{1,2,3}的结果
我们可以很明显的发现,这里如果初始数组为{2,3,1},其排列仅从2,3,1开始,前面的跳过了。
此外,next_permutation(node,node+n,cmp)可以对结构体num按照自定义的排序方式cmp进行排序。