康托逆展开（Cantor inverse expansion）

算法描述

已知 {1, 2, 3, 4, 5} 的全排列，并且已经从小到大排序完毕．

实例一

(1) 找出第96个数

第一步，用96-1得到95

第二步，用95去除4!，得到3余23，有3个数比它小的数是4，所以第一位是4

第三步，用23去除3!，得到3余5，有3个数比它小的数是4，但4已经在之前出现过了，

        所以第二位是5（4在之前出现过，所以实际比5小的数是3个）

第四步，用5去除2!得到2余1，有2个数比它小的数是3，第三位是3

第五步，用1去除1!得到1余0，有1个数比它小的数是2，第二位是2，最后一个数只能是1

所以，这个数是45321

实例二

(2) 找出第16个数

第一步，用16-1得到15

第二步，用15去除4!得到0余15，有0个数比它小的数是1

第三步，用15去除3!得到2余3，有2个数比它小的数是3，但由于1已经在前面出现过了，

        所以这里应该是4（因为1在之前出现过了所以实际比4小的数是2, 3这两个）

第四步，用3去除2!得到1余1，有1个数比它小的数是2，但由于1已经在前面出现过了，

        所以这里应该是3（因为1在之前出现过了所以实际比3小的数是2）

第五步，用1去除1!得到1余0，有1个数比它小得数是2，但由于1，3，4已经在前面出现过了，

        所以这里应该是5（因为1，3，4在之前出现过了所以实际比5小的数是2）

最后，只剩下2了，所以最后一个数只能是2

所以这个数是14352

代码

int fac[]={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

int* uncantor(int x, int k)
{
    int *res, *h;
    int i, j, l, t;

    res = (int *)malloc(k*sizeof(int));
    h = (int *)malloc((k+1)*sizeof(int));
    memset(res, 0, k*sizeof(int));
    memset(h, 0, (k+1)*sizeof(int));

    --x;
    for(i=1; i<=k; i++)
    {
        t = x / fac[k-i];
        x -= t * fac[k-i];

        for(j=1, l=0; l<=t; j++)
            if(!h[j])l++;
        j--;
        h[j] = 1;
        res[i-1] = j;
    }

    return res;
}