全排列

题意：计算0-9的第1000000大的字典序

注意：
标记的数组位置和具体的值恰好相反
求第n个状态则需要转换n-1次

#include <bits/stdc++.h>
using namespace std;

int arr[15] = {9,8,7,6,5,4,3,2,1,0};
const int T = 1000000;
const int M = 9;
int fac[15] = { 1 };

void init()
{
    for (int i=1; i <= 9; i++)
        fac[i] = fac[i-1] * i;
}

int main()
{
    int div,sub = T-1,bit = M;
    init();
    for (int i = 1; i <= M; i++)
    {
        if (T <= fac[i])
        {
            bit = i-1;
            break;
        }
    }
    for (int i = bit; i > 0; i--)
    {
        int pos = i - 1;
        while (sub >= fac[i] && pos >= 0)//注意：问
        {
           swap(arr[i],arr[pos]);
           sub -= fac[i];
           pos--;
        }
    }
    for (int32_t i = M; i >= 0; i--)
    {
        printf("%d", arr[i]);
    }
    printf("
");
    return 0;
}
/*
2783915460
*/