next_permutation

next_permutation()：

• 求“下一个”排列组合

例如

• 三个字符{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, Compare comp);

返回值：

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

复杂度：

• O(n)。

排列的范围：

• [first, last)，包括first，不包括last

 例：hdu 1027  Ignatius and the Princess II

 

•  给定n个数字，从1到n，要求输出第m小的序列。
• 输入：
• 数字n和m组成，1 <= n <= 1000，1 <= m <= 10000。
• 输出：
• 输出第m小的序列

#include<bits/stdc++.h>
using namespace std;
int a[1001];
int main()
{
    int n, m;
    while(cin>>n>>m)
    {
        for(int i=1; i<=n; i++)
            a[i] = i;   //生成一个字典序最小的序列
        int b = 1;
        do
        {
            if(b == m) break;
            b++;
        }
        while(next_permutation(a+1,a+n+1));					  //注意第一个是a+1, 最后一个是a+n
        for(int i=1; i<n; i++)               //输出第m大的字典序
            cout << a[i] << " ";
        cout << a[n] << endl;
    }
    return 0;
}