HDU 1027 正序和逆序的全排列函数

标签（空格分隔）： C++ 算法竞赛 算法

---

题目来源于HDU 1027

    题目描述 

    Now our hero finds the door to the BEelzebub feng5166. He opens the door and finds feng5166 is about to kill our pretty Princess. But now the BEelzebub has to beat our hero first. feng5166 says, "I have three question for you, if you can work them out, I will release the Princess, or you will be my dinner, too." Ignatius says confidently, "OK, at last, I will save the Princess."
    "Now I will show you the first problem." feng5166 says, "Given a sequence of number 1 to N, we define that 1,2,3...N-1,N is the smallest sequence among all the sequence which can be composed with number 1 to N(each number can be and should be use only once in this problem). So it's easy to see the second smallest sequence is 1,2,3...N,N-1. Now I will give you two numbers, N and M. You should tell me the Mth smallest sequence which is composed with number 1 to N. It's easy, isn't is? Hahahahaha......"
    Can you help Ignatius to solve this problem?

    输入

    The input contains several test cases. Each test case consists of two numbers, N and M(1<=N<=1000, 1<=M<=10000). You may assume that there is always a sequence satisfied the BEelzebub's demand. The input is terminated by the end of file.

    输出

    For each test case, you only have to output the sequence satisfied the BEelzebub's demand. When output a sequence, you should print a space between two numbers, but do not output any spaces after the last number.

    样例输入

    6 4
    11 8

    样例输出

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

这么道题。又是我们的伊格内修斯和龙的故事……现在他遇到了一个问题。给一组数字n,m。构建一个1，2，…,n的数列，每一个元素作为对应位上的数字，可以当做100001进制。现在让你对里面的元素随便排列，然后输出排列中第m小的元素。就像上面的例子，如果n=6，那数组为1,2,3,4,5,6，则数字123456就是最小的，123465是第2小的，123546是第3小的，以此类推。我们要输出第m小的。

这时候，要用到我们的全排列函数了，如果现场写完全不可能。
C++中全排列函数有两个，都在“algorithm”中,开头需引用。两个函数分别为

    升序：next_permutation(iterator1，iterator2)
    降序：prev_permutation(iterator1，iterator2)
他们返回值的类型都是bool型，表示是否排序到了最后一种可能，如果排到最后一种了，也就是下一种可能不存在了，就返回false；如果下一种可能还存在，就返回true。
其中的iterator是迭代、迭代器的意思，这个迭代器，就是地址，可以用“数组名+下标”来表示，如答案中的应用。

注意：

1. 两个函数的迭代器都是前闭后开的，取前不取后，做题时容易出错
2. 如果想正确使用这两个函数，那就需要在全排列之前先将他们都正序/逆序排列一遍。比如说，对1~6升序排，就需要先将这六个数组元素排成升序；prev同理

解题的代码如下。去掉注释，就是解题代码，带着注释，就是观察这两个函数运行的实验。

#include <iostream>
#include <algorithm>
#include <cstdio>
#define N 1001
using namespace std;
int a[N];
int main()
{
    int m,n;
    while (scanf("%d %d",&n,&m)!=EOF)
    {
        int p=0;
        for (int i=1;i<=n;i++)
            a[i]=i;
        do
        {
            p++;
            //if (p==m)
            //{
                for (int i=1;i<=n;i++)
                {
                    if (i!=n)
                        printf("%d ",a[i]);
                    else
                        printf("%d\n",a[i]);
                }
            //  break;  
            //}
        }while (next_permutation(a+1,a+n+1));
        cout << p <<endl;
    }
    return 0;
}

如果想看prev，只需要将next换成prev，再将数组正序，也就是line14改成”a[i]=n-i+1;”就行了。还有就是line29的迭代器范围一定注意，是前闭后开的。