MatRush@ZJUT

今天学校圣诞编程组队网络赛出了道排列题，于是在这里记录一下解决全排列及第N个排列问题的字典序算法。
字典序算法中，对于数字1、2、3……n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是54321。
字典序算法如下：
设P是1~n的一个全排列:P = P1P2……Pn = P1P2……Pj-1PjPj+1……Pk-1PkPk+1……Pn
（1）从排列的最右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i|pi （2）在Pj的右边的数字中，找出所有比Pj大的数中最小的数字Pk，即 k=max{i|Pi>Pj}（右边的数从右至左是递增的，因此k是所有大于Pj的数字中序号最大者）
（3）对换Pj，Pk
（4）再将Pj+1……Pk-1PkPk+1Pn反转，即得到排列P的下一个排列。

以下是模拟STL函数next_permutation(num,num+n)实现的代码：

#include <iostream>
#include <algorithm>
using namespace std;
int n,m,i;
int num[1024];
bool next(int n)
{
    int j = -1;
    for (int i = n-2;i >= 0;i--)
        if (num[i] < num[i+1])
        {
            j = i;
            break;
        }//找到第一个比自己后面的元素小的元素，赋给j
    if (j < 0)
        return 0;
    int k;
    for (int i = n-1;i > j;i--)
        if (num[i] > num[j])
        {
            k = i;
            break;
        }//找到右边降序排列中最右边的大于自己的元素，将其位置赋给k
    swap(num[j],num[k]);//交换num[j]和num[k],右边得到一个新的降序排列的序列
    reverse(num+j+1,num+n);//反转右边的序列,使其升序排列
    return 1;
}
int main()
{
    while (scanf("%d%d",&n,&m) != EOF && n && m)
    {
        for (i = 0;i < n;i++)
        {
            //scanf("%d", &num);
            num[i] = i+1;
        }
        sort(num,num+n);
        for (i = 1;i < m;i++)
            next(n);//模拟STL函数next_permutation(num,num+n);
        for (i = 0;i < n;i++)
        {
            printf("%d", num[i]);
            if (i == n-1)
                printf("\n");
        }
    }
    return 0;
}

附上能用next_permutation()函数解决的题：PKU1146、1256、1731、1833、3187
HDU1027