全排列与组合问题暴力dfs 与采用函数：next_permutation\ prev_permutation

bolincharles / 2024-08-07 / 原文

摘要 P1157 组合的输出 P1706 全排列问题 P1088 [NOIP2004 普及组] 火星人 1199 | 全排列（一本通） POJ 1256

next_permutation 产生全排列的强大,一直到昨晚遇到一个对字符串产生全排列的问题才知道这个函数的强大,我们队是按照dfs去搞全排列,然后在进行字符串的匹配,结果写的很长,过程中还各种debug.

next_permutation函数

组合数学中经常用到排列，这里介绍一个计算序列全排列的函数：next_permutation（start,end），和prev_permutation（start,end）。这两个函数作用是一样的，区别就在于前者求的是当前排列的下一个排列，后一个求的是当前排列的上一个排列。至于这里的“前一个”和“后一个”，我们可以把它理解为序列的字典序的前后。

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

 #include <algorithm>

 bool next_permutation(iterator start,iterator end)

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

include

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;
}
结果：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
如果：当我们把while(next_permutation(num,num+3))中的3改为2时，输出就变为了：
1 2 3
2 1 3
由此可以看出，next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列，同时并改变num数组的值。

另外，需要强调的是，next_permutation（）在使用前需要对欲排列数组按升序排序，否则只能找出该序列之后的全排列数。比如，如果数组num初始化为2,3,1，那么输出就变为了：
2 3 1
3 1 2
3 2 1
此外，next_permutation（node,node+n,cmp）可以对结构体num按照自定义的排序方式cmp进行排序。

也可以对字符...

next_permutation 自定义比较函数 POJ 1256

字典序从大到小排序

include

using namespace std;
int main()
{
int num[3]={1,2,3};
sort(num,num+3,greater()); //处理好初始序列最大
do
{
cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
}while(prev_permutation(num,num+3));
return 0;
}