康托展开判重
康托展开:
数学上的一个公式,这个公式在于判断该数全排列下第几个。定义:
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;}
}
更多推荐
康托展开判重
发布评论