[关闭]
@Junlier 2018-09-19T17:12:34.000000Z 字数 1973 阅读 2602

康托展开

数学方法——数论

一、定义

来自网络的定义:

康托展开是一个全排列到一个自然数的双射,常用于构建hash表时的空间压缩。设有n个数,可以有组成不同(种)的排列组合,康托展开表示的就是是当前排列组合在n个不同元素的全排列中的名次。

通俗来讲:

假设有一个排列{1,2,3,4,5},需要你在它的全排列中,找到排名第m的那个排列
全排列的顺序就是字典序越来越大的排列,和我们的next_permutation()函数的顺序一样

二、怎么实现?

首先,放一个很重要的公式(暂时不需要理解,后面慢慢就懂了):


其中 是阶乘的意思
我们再看一个表格
你先不管它的康托展开那一栏,根据后面的讲解再看

排列组合 名次 康托展开
123 1 0 * 2! + 0 * 1! + 0 * 0!
132 2 0 * 2! + 1 * 1! + 0 * 0!
213 3 1 * 2! + 0 * 1! + 0 * 0!
231 4 1 * 2! + 1 * 1! + 0 * 0!
312 5 2 * 2! + 0 * 1! + 0 * 0!
321 6 2 * 2! + 1 * 1! + 0 * 0!

思考一下
为什么当前数列是排在第x位而不是更靠前?
是不是因为有大数字占领了前面的小数字的位置,把小数字挤到了后面的位置上,所以字典序变大了
这个可以理解吧
那么,我们来考虑每个大数字对整个排列的编号的影响

  • 如果有一个数v[j]在v[i]后面且比v[i]小(也就是(v[j]<v[i]&&i<j))
    那么这个“大”数字就一定会使这个排列的排名(康托展开值)造成影响(变大)
  • 根据上表的展开部分
    位置在i位(这里是指倒过来的第i位)上的数后面有ss个比它小的数,那么我们可以认为它占领了!(i-1)*ss个排列顺序。
    为什么呢,拿出纸笔,随便找个例子,把它单独影响而占领的那几个排列列出来看一看就一目 了然了(我就是这么懂的)
  • 不可能马上就可以明白,对着上面的表格全部算一遍吧

再举个例子:
在(1,2,3,4,5)5个数的排列组合中,计算 34152的康托展开值。

  1. 首位是3,则小于3的数有两个,为1和2,a[5]=2,则首位小于3的所有排列组合为 a[0]*(5-1)!
  2. 第二位是4,则小于4的数有两个,为1和2,注意这里3并不能算,因为3已经在第一位,所以其实计算的是在第二位之后小于4的个数。因此a[4]=2
  3. 第三位是1,则在其之后小于1的数有0个,所以a[3]=0
  4. 第四位是5,则在其之后小于5的数有1个,为2,所以a[2]=1
  5. 最后一位就不用计算啦,因为在它之后已经没有数了,所以a[1]固定为0根据公式:
    X = 2 * 4! + 2 * 3! + 0 * 2! + 1 * 1! + 0 * 0!
    = 2 * 24 + 2 * 6 + 1
    = 61

所以比 34152 小的组合有61个,即34152是排第62。

代码实现就很简单了(其实找后面有几个比v[i]小有各种方法log(n)!)

  1. for(int i=1;i<=n;++i)//注意这里i全部是正着枚举的
  2. //所以下面的jc处是n-i
  3. {
  4. int ss=0;//意思同上
  5. for(rg int j=i+1;j<=n;++j)//找后面比v[i]小的
  6. if(v[j]<v[i])ss++;
  7. num+=ss*jc[n-i];//jc是阶乘(预处理好的数组)
  8. }
  9. num++;//加上1是显然的(61个在我前面,那我就排62)

三、补充:逆康托展开

其实和康拓展开差不多,总体思想很简单,再用一下上面的例子,我们通过34152的一系列计算得到了62,那我们肯定可以根据62倒退回去,具体如下:

  • 首先肯定把62减回去到61才好算 ^_^
  • 然后:
    1.用61/(!4)=2余13,说明a[5]=2,说明比首位小的数有2个,所以首位为3。
    2.用13/(!3)=2余1,说明a[4]=2,说明在第二位之后小于第二位的数有2个,所以第二位为4。
    3.用1/(!2)=0余1,说明a[3]=0,说明在第三位之后没有小于第三位的数,所以第三位为1。
    4.用1/(!1)=1余0,说明a[2]=1,说明在第二位之后小于第四位的数有1个,所以第四位为5。
    5.最后一位自然就是剩下的数2啦。
    6.通过以上分析,所求排列组合为 34152。

恩,那个代码我打的纯暴力

  1. num--;
  2. for(rg int i=1;i<n;++i)
  3. {
  4. rg int kk=num/jc[n-i]+1;//向上面讲解里那样计算
  5. //+1不用解释吧,x个比我小,我就是第x+1个
  6. rg int z=0;//计录当前到第几小了
  7. num=num%jc[n-i];//同上
  8. for(rg int j=1;j<=n;++j)//找没有用过(没有排在左边)第kk小的数
  9. {
  10. if(!b[j])z++;//没用过
  11. if(z==kk)
  12. {
  13. printf("%d ",j);//就是你了
  14. b[j]=1;break;//标记用过
  15. }
  16. }
  17. }
  18. //暴力到极致了吧……

四、题目

推荐板子:luoguP3014牛线

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注