康托展开：

康托展开：

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

康托展开的作用是求n个数的全排列中某一个序列在所有排列中的次序(该排列次序(亦称之为排名)以字典序从小到大排序)

在n=3的全排列中,{1,3,2}排第几位。

可以写出n=3的全排列 {1,2,3}，{1,3,2}，{2,1,3}，{2,3,1}，{3,1,2}，{3,2,1}

所以容易看出{1,3,2} Rank 2

康托展开的公式:

X=a[n] * [(n-1)!] +a[n-1]*[(n-2)!]+....+a[1] * [0!]。

其中X代表当比前排列小的排列的个数,

a[i]代表当前排列里从i位置右侧比i位置的数小的数的个数。

在n=5的全排列中,计算{3,4,1,5,2}的康托展开值。

首位是3,则小于3的数有两个,为1和2,a[5]=2,则首位小于3的所有排列组合为a[5]*(5-1)!

第二位是4,则小于4的数有两个,为1和2,注意这里3并不能算，因为3已经在第一位，所以其实计算的是在第二位之后小于4的个数。因此a[4]=2。

第三位是1,则在其之后小于1的数有0个,所以a[3]=0。

第四位是5,则在其之后小于5的数有1个,为2,所以a[2]=1。

最后一位就不用计算啦,因为在它之后已经没有数了,所以a[1]固定为0.

根据公式：

      rank=2*(4!)+2*(3!)+0*(2!)+1*(1!)+0*(0!)=61.

所以比{3,4,1,5,2}小的组合有61个,即{3,4,1,5,2}排名62。