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

例如：{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为数组名 这个式子是求数组的长度。

代码：

1 #include 
     
       2  3 const int fac[] = {
   1, 1, 2, 6, 24, 120, 720, 5040, 40320};//阶乘 4  5 int KT(int a[],int n) 6 { 7     int i, j, cnt, sum; 8     sum = 0; 9     for(i=0;i
      
       a[j]) cnt++;15         }16         sum = sum + cnt * fac[n-i-1]; 17     }18     return sum;19 }20 21 int main()22 {23     int s[] = {
   1,3,5,2,6,4};24     int re;25     re = KT(s,sizeof(s)/sizeof(*s));26     printf("%d",re+1);27     return 0;28 }