求第一百万个字典序排列数

原题：https://projecteuler.net/problem=24

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

题目大意：

求 (0,1,2,3,4,5,6,7,8,9) 的第一百万个字典序排列

解题思路：

• 直接一个一个进行DFS会比较耗时
• 可以通过数学方法来进行判断，从左往右，最高位上有10种数字选择，最高位上选定后，对应后面共有种排列，因此对于最高位上，从0,1,2,3...开始，每个数字共有种排列，比如，最高位初始从0开始，共有种排列；接下来，最高位为1，又有种排列；然后最高位为2，又有种排列；此时一共有 种排列，此时已经超过一百万，因此，最高位为2时，并没有排完每一个排列；因此把最高位定为2，根据一百万减去前面的排列数目，即接下来要求的排列数目，确定次高位，依次确定每一位；
  • 这里要注意如果刚好排完，即比如最开始要求的就是求第个排列，就是求当前剩余数字的最后一个排列，即把剩下的数字按照从大到小的顺序排列即可

代码如下：

#include<iostream>
#include<cstring>
using namespace std;

int main()
{
    int i = 0;
    int j = 0;
    int left[10] = {0};
    int used[10]={0};
    long temp = 1;
    long temp_10 = 1;
    long num = 1000000; // 注意整除时的情况

    for(i = 0; i < 10; ++ i)
    {
        if(num==0) // 特殊情况，如果能够整除，那么说明是当前剩下数字的最后一个排列，即这个排列就是从大到小进行排列
        {
            for(j = 9; j >=0; --j)
                if(used[j]==0)
            {
                left[i] = j;
                ++i;
            }
        }
        else // 一般情况，计算每一位上的每个数字有多少种组合，然后确定当前的数字
            {
                temp = 1;
                for(j = 10-i; j > 0; --j)
                {
                    temp *= j;
                }
                temp_10 *= 10;
                temp /= (10-i);
                left[i] = num / temp;
                num = num - left[i]*temp;

                int count = 0;
                for(j = 0; j < 10; ++j)
                {
                    if(num !=0 && count == (left[i]+1))// 如果能整除，那么应该是第 left[i] + 1 个数字
                        break;
                    else if(num==0 && count==left[i]) // 如果不能整除，那么应该是第 left[i] 个数字
                        break;
                    if(used[j] == 0)
                       ++count;
                }
                left[i] = j-1;
                used[left[i]]=1;
            }
    }
    for(i = 0; i < 10; ++i)
    {
        printf("%d",left[i]);
    }
}