next_permutation应用

STL 提供求下一个排列组合的函数 next_permutation()。例如 3 个字符 a, b, c 组成的序列，next_permutation() 能按字典返回 6 个组合，即 abc, acb, bac, bca, cab, cba

next_permutation() 的定义有下面两种形式：

• bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

• bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Comparecomp);

返回值：如果没有下一个排列组合，返回false，否则返回true。每执行一次，就会把新的排列放到原来的空间里

样例：Ignatius and the Princess II (HDU 1207)

给定 n 个数字，从 1 到 n ,要求输出第 m 小的序列。

输入：数字 n 和 m ，1 <= n <= 1000, 1 <= m <= 10000;

输出：输出第 m 小的序列

Sample Input

6 4
11 8

Sample Output

1 2 3 5 6 4
1 2 3 4 5 6 7 9 8 11 10

思路： 首先生成一个 1 2 … n 的最小字典序列，然后用 next_permutation() 一个一个生成字典序更大的序列

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;

int a[N];
int n, m;

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    while(cin >> n >> m){
        for(int i = 1; i <= n; i ++) a[i] = i; // 生成一个字典序最小的序列
        int k = 0;
        do{
            if(k == m) break;
            k ++;
        }
        while(next_permutation(a + 1, a + 1 + n));
        for(int i = 1; i <= n; i ++){
            cout << a[i] << ' ';
        }
        cout << '\n';
    }


    return 0;
}