STL（三）——next_permutation（）

一. next_permutation()介绍

在STL中，除了next_permutation外，还有一个函数prev_permutation，两者都是用来计算排列组合的函数。
前者是求出下一个排列组合，而后者是求出上一个排列组合。
对序列 {a, b, c}，按照字典序列，每一个元素都比后面的小。
固定a之后，a比b、c都小，c比b大，它的下一个序列即为{a, c, b}；
而{a, c, b}的上一个序列即为{a, b, c}。
同理可以推出所有的六个序列为：{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a}，
其中{a, b, c}没有上一个元素，{c, b, a}没有下一个元素。

二.例题

HDOJ 1027 Ignatius and the Princess II

Problem Description
给定一个从1到N的序列，我们定义1,2,3 ... N-1，N 是所有可以由1到N组成的序列中最小的序列（每个数字在此问题中仅使用一次。）因此，很容易看到第二个最小的序列是1,2,3 ... N，N-1。
现在我将给您两个数字N和M。告诉我第N个最小的序列，该序列由1到N组成。

Input
输入包含几个测试用例。每个测试用例均由两个数字N和M（1 <= N <= 1000，1 <= M <= 10000）组成。您可以假设始终有一个满足需求的序列。输入在文件末尾终止。

Output
对于每个测试用例，只需要输出满足需求的序列即可。输出序列时，应在两个数字之间打印一个空格，但不要在最后一个数字之后输出任何空格。

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

#include<bits/stdc++.h>
using namespace std;
int a[1005];
int main() {
  int n, m;
  while (~scanf("%d%d", &n, &m)) {
    //数组赋值为最小情况1~n 
    for (int i = 0; i < n; i++) a[i] = i+1;
    //初始为最小情况才能使用next_permutation()
    int count = 1;
    do {
      if (count == m) break;
      count++;
    //重排列后会保存到原空间 
    } while(next_permutation(a, a+n));
    cout << a[0];
    for (int i = 1; i < n; i++)
      printf(" %d", a[i]);
    printf("\n");
  }
}