康托展开式及其逆过程

康托展开式：

　　X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! ，其中a[i]表示在未出现的元素中比当前元素小的个数。康托展开式可用于求一个排列位于全排列的第几个。同样，其逆过程可以求在全排列中的第k个排列是多少。具体实现如下：

例题1：

给出一个数字n和一个排列，返回这个排列在数字1-n的全排列（按字典序）中排第几位。其中，编号从1开始。例如，排列 [1,2,3] 在数字{1，2，3}的全排列中是第 1 个排列，排列[1, 3, 2]在数字{1，2，3}的全排列中是第2个排列。以此类推，以下是数字{1，2，3}的全排列及其编号：

1 2 3 | 1
1 3 2 | 2
2 1 3 | 3
2 3 1 | 4
3 1 2 | 5
3 2 1 | 6

int getIndex(int n, vector<int> &numbers)
{
    if(n<=0 || numbers.size()!=n)return -1;
    if(n==1)return 1;
    vector<int> fact(n, 1);//先生成阶乘数组 
    for(int i=1; i<fact.size(); ++i)fact[i]=fact[i-1]*i;
    int sum=0;
    for(int i=0; i<numbers.size(); ++i)
    {
        int count=0;
        for(int j=i+1; j<numbers.size(); ++j)
        {
            if(numbers[j]<numbers[i])++count;
        }
        sum=sum+count*fact[n-i-1];
    }
    return sum+1;
}

康托展开式的逆过程的求法也可以作为求1至n的数字的全排列的非递归实现方法，其逆过程可实现为

vector<int> getArray(int n, int k)
{
    if(n<=0)return vector<int>();
    vector<int> fact(n+1, 1);//先生成阶乘数组 
    for(int i=1; i<fact.size(); ++i)fact[i]=fact[i-1]*i;
    if(k>fact[n])return vector<int>();
    --k;
    vector<bool> flag(n+1, false);//标记哪个数字没用过
    vector<int> result;
    for(int i=0; i<n; ++i)
    {
        int count=k/fact[n-i-1];
        for(int i=1; i<flag.size(); ++i)
        {
            if(flag[i]==false)--count;
            if(count==-1){
                flag[i]=true;
                result.push_back(i);
                break;
            }
        }
        k=k%fact[n-i-1];
    }
    return result;
}