查看“︁康托展开”︁的源代码

'''康托展开'''是一个全排列到一个[[自然数]]的[[双射]]，常用于构建[[哈希表]]时的空间压缩。
康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

以下称第x个全排列都是指由小到大的顺序。

==公式==
<math>X=a_n(n-1)!+a_{n-1}(n-2)!+\cdots+a_1\cdot0!</math>

其中,<math>a_i</math>为整数,并且<math>0\leq a_i<i,1\leq i\leq n</math>。

<math>a_i</math>的意义参见举例中的解释部分

===举例===

例如，3 5 7 4 1 2 9 6 8 展开为 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位（0~n-1）全排列后，其康托展开唯一且最大约为n!，因此可以由更小的空间来储存这些排列。由公式可将X逆推出唯一的一个排列。

==康托展开的逆运算==

既然康托展开是一个双射，那么一定可以通过康托展开值求出原排列，即可以求出n的全排列中第x大排列。

如n=5,x=96时：

 首先用96-1得到95，说明x之前有95个排列.(将此数本身减去1)
 用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.

按以上方法可以得出通用的算法。

==参考文献==
# {{Cite book | author =  Thomas H. Cormen (EDT),Charles E. Leiserson, Ronald L. Rivest, Clifford Stein | title = Introduction to Algorithms,Third Edition | location = USA | publisher = The MIT Press ||ISBN = 978-0-262-03384-8| language= en|}}

[[Category:搜尋演算法]]