康托展开及其应用

《康托展开及其应用》由会员分享，可在线阅读，更多相关《康托展开及其应用（2页珍藏版）》请在金锄头文库上搜索。

1、康拓展开及其应用康托展开是一个全排列到一个自然数的双射，常用于空间压缩，例如一个 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、个，因此第一项为 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代码实现