资源预览内容
亲,该文档总共2页全部预览完了,如果喜欢就下载吧!
资源描述
康拓展开及其应用康托展开是一个全排列到一个自然数的双射,常用于空间压缩,例如一个 9 的全排列,只需要 962879 个存储单位即可全部存储。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。公式cantor=an*(n-1)!+an-1*(n-2)!+.+ai*(i-1)!+.+a1*0!其中,ai为整数,并且 0=aii,1=i=n。举例例如,357412968 展开为 98884。因 X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884.解释:排列的第一位是 3,比 3 小的数有两个,以这样的数开始的排列有 8!个,因此第一项为 2*8!排列的第二位是 5,比 5 小的数有 1、2 、3、4,由于 3 已经出现,因此共有 3 个比 5小的数,这样的排列有 7!个,因此第二项为 3*7!以此类推,直至 0*0!用途:显然,n 位(0n-1)全排列后,其康托展开唯一且最大约为 n!,因此可以由更小的空间来储存这些排列。由公式可将 X 逆推出对应的全排列。康托展开的逆运算既然康托展开是一个双射,那么一定可以通过康托展开值求出原排列,即可以求出 n的全排列中第 x 大排列。如 n=5,x=95 时:用 95 去除 4! 得到 3 余 23,说明有 3 个数比第 1 位小,所以第一位是 4用 23 去除 3! 得到 3 余 5,说明有 3 个数比第 2 位小,所以是 4,但是 4 已出现过,因此是 5用 5 去除 2!得到 2 余 1,类似地,这一位是 3用 1 去除 1!得到 1 余 0,这一位是 2最后一位只能是 1所以这个数是 45321代码实现
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号