上一个排列和下一个排列
next_permutation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 组合数学中经常用到排列，这里介绍一个计算序列全排列的函数：next_permutation（start,end），和prev_permutation（start,end）。这两个函数作用是一样的，区别就在于前者求的是当前排列的下一个排列，后一个求的是当前排列的上一个排列。至于这里的“前一个”和“后一个”，我们可以把它理解为序列的字典序的前后，严格来讲，就是对于当前序列pn，他的下一个序列pn+1满足：不存在另外的序列pm，使pn<pm<pn+1.
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define ll long long
using namespace std;
int main()
{
int a[3]={1,2,3};
sort(a,a+3);
do{
for(int i=0;i<3;i++)
cout<<a[i]<<" ";
cout<<endl;
}while(next_permutation(a,a+3));
return 0;
}
|
结果为
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
prev_permutation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define ll long long
using namespace std;
int main()
{
int a[3]={3,2,1};
do{
for(int i=0;i<3;i++)
cout<<a[i]<<" ";
cout<<endl;
}while(prev_permutation(a,a+3));
return 0;
}
|
结果为
3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3