基本内容
函数原型：bool next_permutation(iterator start, iterator end);
返回值：布尔型
函数本体：
next_permutation(开始，结束)，输出所有比当前排列大的排列，顺序是从小到大。
prev_permutation(开始，结束)，输出所有比当前排列小的排列，顺序是从大到小。
注意：这两个函数的排列区间都是左闭右开，如 next_permutation(a,a+10) ，被全排列的区间为[0,10),即数组中下标为 0 1 2 3 4 5 6 7 8 9 的元素。
样例1 普通数组全排列
普通数组可以通过数组名表示地址，非常容易实现
#include<iostream>
#include<algorithm>//使用 next_permutation()和sort()需要导入的头文件
//可以使用万能头文件代替上面两个头文件使用
using namespace std;
int main(){
int a[4]={2,1,4,3};
sort(a,a+4);//对数组排序
do{
for(int i=0;i<4;i++){//打印排列
cout<<a[i]<<' ';
}
cout<<endl;
}while(next_permutation(a,a+4));//获取下一个排列
return 0;
}
样例2 结构体全排列
结构体默认是不能比较大小的，那么就不能使用默认的next_permutation()排列比较函数，需要使用自定义排列比较函数
#include<iostream>
#include<algorithm>//使用 next_permutation()和sort()需要导入的头文件
using namespace std;
struct test{//结构体test
int val;
};
bool cmp(test t1,test t2){//自定义的排列
return t1.val<t2.val;
}
int main(){
test t[4];//结构体数组
t[0].val=1;
t[1].val=2;
t[2].val=3;
t[3].val=4;
do{
for(int i=0;i<4;i++){//打印排列
cout<<t[i].val<<' ';
}
cout<<endl;
}while(next_permutation(t,t+4,cmp));//获取下一个排列
return 0;
}
样例2 vector全排列
vector及string等数据结构不能直接用名字代表地址，只能够使用自带的迭代器begin()、end()实现全排列
#include<iostream>
#include<vector> //使用vector需要导入的头文件
#include<algorithm>//使用 next_permutation()和sort()需要导入的头文件
using namespace std;
int main(){
vector<int> v;//定义一个int型的vector
v.push_back(1);//在尾部插入数据1
v.push_back(2);
v.push_back(3);
v.push_back(4);
do{
for(int i=0;i<v.size();i++){//打印排列
cout<<v[i]<<' ';
}
cout<<endl;
}while(next_permutation(v.begin(),v.end()));//获取下一个排列
return 0;
}
注::prev_permutation拥有同样的用法，大家可以动手尝试一下
真题
将 1,2,…,9 共 9 个数分成三组，分别组成三个三位数，且使这三个三位数的比例是a : b : c，试求出所有满足条件的三个三位数，若无解，输出 No!!!。
输入描述：
三个数，a, b, c（a<b<c）
输出描述：
若干行，每行 3 个数字。按照每行第一个数字升序排列。
示例 1：
输入：
1 2 3 输出：
192 384 576
219 438 657
273 546 819
327 654 981
思路 本解法采用9个数排列,枚举每一种情况， 使用 c++中的 next_permutation 函数获得下一个排列。
#include <bits/stdc++.h>
using namespace std;
//全排列
int s[10]={0,1,2,3,4,5,6,7,8,9};
int main()
{
int a,b,c,x,y,z;
cin>>a>>b>>c;
int cnt=0;
do{
x=100*s[1]+10*s[2]+s[3];//第一个数
y=100*s[4]+10*s[5]+s[6];//第二个数
z=100*s[7]+10*s[8]+s[9];//第三个数
if(x*b==y*a && y*c==z*b){
cnt++;
cout<<x<<" "<<y<<" "<<z<<endl;
}
}
while(next_permutation(s+1,s+10));//减少排列次数
if(cnt==0){
printf("No!!!");
}
return 0;
}