康托展开

康托展开:求一组数在全排列中第几小

例如：{1 ,2, 3, 4, 5, 6} 求 135264 在全排列中的第几小？

时间复杂度：

康托展开 O(n)

原理: 康托展开的公式是 X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0! 其中，ai为当前未出现的元素中是排在第几个（从0开始）。

1是当前未出现的数字中最小(第0小）所以 0*5! 因为1排在第一个位置 后面有5个数 所以是5!

3是当前未出现的数字中第一小 所以1*4!

5是当前未出现的数字中第二小 所以2*3!

下面依次类推

X=0*5! + 1*4! + 2*3! + 0*2! + 1*1! + 0 =37

也就是说 135264 在全排列中 它的前面还有37个比它小的数字

所以 它是第38小的数字。

sizeof(s)/sizeof(*s) s为数组名 这个式子是求数组的长度。

代码：

#include <cstdio>

const int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};//阶乘

int KT(int a[],int n)
{
    int i, j, cnt, sum;
    sum = 0;
    for(i=0;i<n;i++)
    {
        cnt = 0;
        for(j=i+1;j<n;j++)
        {
            if(a[i]>a[j]) cnt++;
        }
        sum = sum + cnt * fac[n-i-1]; 
    }
    return sum;
}

int main()
{
    int s[] = {1,3,5,2,6,4};
    int re;
    re = KT(s,sizeof(s)/sizeof(*s));
    printf("%d",re+1);
    return 0;
}