序列中各个元素都不相同，将这个序列进行全排列，并且将所有排列从小到大排序。现在给定一个序列，确定这是第几个排列。以及它的逆问题：确定第k个排列是什么。这可用Cantor展开以及逆Cantor展开。 康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。

例如，N=4的不重复序列\( (1,2,3,4) \) 共有4!种排列，1234,1243,1324,2431,3412,4321等等。按字典序应该是1234, 1243, 1324, 1342, 1423, 1432,… 。虽然可以通过C++ STL的next_permutation（begin, end）可计算下一个全排列，理论上你要算n个数的第k个排列只需要调用k-1次next_permutation()就行，但是next_permutation的时间复杂度是O(n)，要调用多次才能算出第k个排列，效率不够高。

而康托展开只要O(n)的时间就可以计算出这个序列是第几个排列。

\( (a_n,a_{n-1},..,a_2,a_1) \) 排列在n!个阶乘中的序数X为：

其中\( p_k \)表示\( a_k \) 到\( a_1 \)中小于\( a_k \)的个数。

举个例子来说，判断34152是12345的第几个排列数。即\( a_5=3,a_4 =4,a_3 =1,a_2 =5,a_1 =1 \)。首先得到各个 \( p_i\):
p_5 是\( (a_5,…,a_1) \)中小于\( a_5 =3 \)的数量，只有1和2满足所以\( p_5 =2 \)。\(p_4 \)是\( (a_4,…,a_1)\)中小于\( a_4=4 \) 的个数，为2。类似地，\( p_3=0 ，p_2 =1,p_1 =0 \)

这样，
\[\begin{align}X &= p_5\cdot4! + p_4 \cdot 3! + p_3 \cdot 2! + p_2 \cdot 1! +p_1 \cdot 0! \\
&= 2\cdot4! + 2 \cdot 3! + 0 + 1 \cdot 1! +0\\
&= 48+12+1 = 61 \end{align} \],说明这个序列34152是12345的排列中第62小的序列

康托展开的的逆过程，即由一个\( [0,n!-1] \)中的正整数m转换为长为n的全排列，可参阅 《 序数法：一种排列的生成算法 》

#include <cstdio>
#include <cstring>
#define MAXN 20
int fact(int x)
{
    int t=1;
    for(int i=1;i<=x;i++)
    {
        t*=i;
    }
    return t;
}
int cantor(int x)
{
    char a[MAXN];
    int p[MAXN];
    int i,N ;
    sprintf(a,"%d",x);
    for(i=0;a[i];i++)
    {
        a[i]=a[i]-'0';
    }
    N=i;
    for(i=0;i<N;i++)
    {
        p[i] =0;
        for(int j=i+1;j<N;j++)
        {
            if(a[j]<a[i])
            {
                p[i]++;
            }
        }
    }
    int X=0;
    for(i=0;i<N;i++)
    {
        X+=p[i]*fact(N-i-1);
    }
    return X;
}
int main(void)
{
    int N;
    scanf("%d",&N);
    printf("%d\n",cantor(N));
    return 0;
}