康托展开判重

康托展开判重

康托展开：

数学上的一个公式，这个公式在于判断该数全排列下第几个。定义：

eg：数213在123的全排列下面是第X+1个数

        2的后面有1个数比2小，既1*2！

        1的后面没有比1小的数，既0*1！

        3的后面没有比3小的数，既0*0！

        X = 1*2！+0*1！+0*0！ = 2

        123的全排列： 123  132  213 231 312 321

九宫最多有9！种排列组合，既362880中排列组合方式，使用数组state[362880]可以用来判断是否出现重复的元素。

bool state[362880];       //N的阶乘int kangtuo(int x[])  //康拓展开进行判重
{int fac[]={1,1,2,6,24,120,720,5040,40320};int i,j,t,sum;sum = 0;for(i=0;i<9;i++){t = 0;for(j=i+1;j<9;j++){if(x[j]<x[i])t++;}sum = sum+t*fac[8-i];}if(state[sum]==1)return 0;else{state[sum] = 1;return 1;}
}