康托展开及其逆运算

xiaoxiao2021-02-28  16

康托展开的定义:

对于n元素的整数数组,第i元素(从1开始)在数组中按大小顺序的位置应为:a[i]*(n-i)!(a[i]为后续元素中小于该元素的个数)

例如:数组213,对第1元素“2”计算,a[1]=1(小于2的只有1,为1个),a[1]*2!=1*2=2,即“2”按大小顺序为第2个

那么,对所有元素展开计算求和:X=a[1]*(n-1)!+a[2]*(n-2)!+…+a[i]*(n-i)!+…+a[n]*0!,得到的X是该数组在全排列数排中比该数小的个数

例如:

2143 这个数,求其展开:

从头判断,至尾结束,

① 比 2(第一位数)小的数有多少个->1个就是1,1*3!

② 比 1(第二位数)小的数有多少个->0个0*2!

③ 比 4(第三位数)小的数有多少个->3个就是1,2,3,但是1,2之前已经出现,所以是  1*1!

将所有乘积相加=7

比该数小的数有7个,所以该数排第8的位置。

1234  1243  1324  1342  1423  14322134  2143  2314  2341  2413  24313124  3142  3214  3241  3412  3421

4123  4132  4213  4231  4312  4321

康托展开逆运算:

现已知X,求该数组。例如求4数数组中第9位置的数组:

X=9-1=8, 

8/3!=1余2,

2/2!=1余0,

0/1!=0余0,

0/0!=0

上式表示a[1]=1,a[2]=1,a[3]=0,a[4]=0。由此得知第一位数为2,后续数为3、1、4,因此数组为2314

转载请注明原文地址: https://www.6miu.com/read-2649957.html

最新回复(0)