原理"/>
康托展开原理
康托展开结合组合数学会比较容易理解。
假设有 {1, 2, 3} 这三个数,那么全部的排列组合有 6种,按从小到大的顺序有 123, 132,213, 231, 312, 321。
而康托展开能以n^2的时间复杂度求出比某个排序组合小的个数。比如说 比 213 小的数有2个,比312小的数有4个。
原理:
假设有 {1,2, 3, 4} 这4个数,根据组合数学的知识,一共有 4*3*2*1种排序组合。
3***,这种排序组合且比这种排序组合都小的个数有多少?很明显是 3*3!。
34**,这种排序组合且比这种排序组合都小的个数有多少? 2*3!+ 3*2!。
等式包含两大类,一类是比34**所有组合都小的,即以1为首和以2为首的所有组合 2*3!,还有31**, 32**的所有组合 2*2!。另一类是34**的所有组合 2!。
同样的,342*,这种排序组合且比这种排序组合都小的个数有多少?比342*都小的分别有 1***,2***,31**,32**,341*,即2*3!+2*2!+1!,而342*这种组合有 1!。一共有2*3!+2*2!+2*1!。
对于3421这种排序组合,我们只求比这种排序组合小的个数有多少,总结上面的内容,比3421小的组合有1***,2***,31**,32**,341*,即 2*3!+2*2!+1*1!。
根据上面所讲的,康托展开的原理就是从某个排序组合的首位开始,找出比当前这位数小的个数,且之前没有出现过的数的个数乘以对应的阶乘,结果累加就是我们要求的值。
比如说3421,从首位3开始,比3小的之前没出现过的数有1,2,那么就有 2*3!。
第二位是4,比4小的数有1,2,3,但是3已经出现在首位了,所以总共只有2个,即1,2,那么就有2*2!。
第三位是2,比2小的数有只有1,而且首位和第二位都不是1,那么就有1*1!。
通过这种方法就能很快的求出比某个排序组合小的总个数。
这种技巧也能够运用在状态压缩上面,某个排序组合有 x个比它小的排序组合,那么可以给这种排序组合编号为x,可以保证不会有编号重叠的情况,实现符号压缩。
在已知编号的情况下,也能够通过编号还原排列组合。顺序反过来就行了。
int cantor(char* ss) { // 先往 n[] 存放阶乘的结果int ret = 0;for(int i = 0; i < 9; ++i) {int cnt = 0;for(int j = i+1; j < 9; ++j) {if(ss[j] < ss[i]) cnt++;}ret += cnt*n[8-i];}return ret;
}void decantor(int num, char *ss) {int p = 0; bool v[10];memset(v, false, sizeof(v));for(int i = 8; i >= 0; --i) {int cnt = 0, tmp = num/n[i];num %= n[i];for(int j = 0; j < 9; ++j) {if(v[j]) continue;if(cnt == tmp) {ss[p++] = j+'0';v[j] = true;break;}cnt++;}}ss[p] = '\0';
}
更多推荐
康托展开原理
发布评论