发布时间:2022-12-04 14:00
STL提供了两个用来计算排列组合关系的算法,分别是next_permutation和prev_permutation。
next_permutation通常用于生成序列的全排列。
函数原型:
bool next_permutation(iterator start,iterator end);
用法
int a[] = {1, 2, 3};
do{
cout << a[0] << " " << a[1] << " " << a[2] << endl;
}while(next_permutation(a, a + 3));
//若当前调用排列已经达到最大字典序,比如321,则函数返回false,否则返回true
//如果函数参数改为(a, a + 2),则可以只对部分长度全排列
next_permutation如何生成下一个全排列?
1.从最右边开始,两两比较相邻的元素,直到找到右边比左边大的一对,左边那个就是将要被替换的;
2.再从最右边开始找比这个元素大的第一个,交换他们两个;
3.交换之后,翻转交换元素的后面的所有元素;
例如:
1 3 4 6 5 2 -> 1 3 5 6 4 2 -> 1 3 5 2 4 6
1.从右边开始比较5 2
比较6 5
比较4 6 找到了右边比左边大
2.然后从右边开始找比左边元素大的第一个
2比4小
5比4大 找到了5
将5与4交换
序列变为 1 3 5 6 4 2
3.相较于原序列1 3 4 6 5 2
4于5交换了位置,序列字典序已经变大
若要生成下一个字典序的全排列,还要将4后边元素翻转,得到下一个最小字典序列。
即4后边三位 6 4 2 -> 2 4 6
最终序列 1 3 5 2 4 6 就是原序列的下一个全排列。
于next_permutation相对应,求上一个全排列prev_permutation
用法
int a[] = {3, 2, 1};
do{
cout << a[0] << " " << a[1] << " " << a[2] << endl;
}while(prev_permutation(a, a + 3));
例:第M个数列
题目描述
Problem Description
给定1到N的序列,我们定义1,2,3 …N-1,N是由1到N组成的所有序列中的最小序列(每个数字只能使用一次)。则很容易看出,第二个最小的序列是1,2,3 … N,N-1。
现在,给定两个数字N和M,请告诉由数字1到N组成的第M个最小的序列是什么。
Input
输入包含多组测试数据,请处理到文件结束。
每组测试数据包含两个整数N和M(1<=N<=1000, 1<=M<=10000)。
数据保证一定有满足要求的数列。
Output
请输出满足要求的数列。数列的两个数之间用1个空格隔开,并且最后一个数后面没有空格。
每组数据输出一行。
输入样例
6 4
11 8
输出样例
1 2 3 5 6 4
1 2 3 4 5 6 7 9 8 11 10
//第M个数列
#include
using namespace std;
int main(){
int N, M;
while(cin >> N >> M){
vector a;
for(int i = 1; i <= N; i++) a.push_back(i);
vector::iterator it = a.begin();
int cnt = 0;
do{
if(cnt == M - 1){
for(int i = 0; i < N; i++){
if(i == N - 1) cout << a[i] << endl;
else cout << a[i] << " ";
}
break;
}
cnt++;
}while(next_permutation(it, it + N));
}
return 0;
}