算法详解——康托展开/逆康托展开


Warning


由于本博客作者实在是太弱啦,本篇文章可能存在大量的错误,漏洞,不规范,不合法之处。若您发现本文章所存在的任何问题,请您尽快在评论区指出,十分感谢!

另外,本文随意转载,但请注明出处。

问题


给出一个 n, 一个 1~n 的排列,问对于 1~n 的全排列,该排列按照字典序排名为多少.

n≤20

解答


此题需要用康拓展开解决,下面会给出一些介绍。

康拓展开是一种 n 的全排列与自然数空间 {0,1,2,..., n! -1} 的映射,简单的说,就是每一个全排列都有一个唯一的自然数与其对应,康托展开可以使我们找到这个自然数,显然,它是可逆的,我们可以通过逆康托展开找到某自然数对应的全排列.

所以显然,它是一种特殊的,毫不浪费空间的,无冲突的哈希函数,它具有如此优良的性质,那么它是如何映射的呢?下面给出公式:
$$X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[1]*0!$$

a[i] 的含义将在随后的程序讲解中给出,下面我们尝试从本质上理解一下康托展开。如果不想看,完全可以跳过看应用部分,由于博主太弱,此处可能有模糊/不正确之处,欢迎神犇批判。

变进制


常见的进制有二进制、八进制、十进制、十六进制等,这些“常数进制”都是合法的计数方式,对于 p 进制数,采取“满 p 进 1”的方式,也就是说,p 进制数 K 可以表示为:

$$K=a[1]*p^{1}+a[2]*p^{2}+...+a[n]*p^{n}$$

然而,除此之外,我们还可以通过变进制来表示一个数,需要注意的是,并非随便一种变进制的策略都是合法的,下面给出一种合法的变进制数:

它的运算规则是这样的:对于第一位,满 2 进 1,第二位,满 3 进 1,以此类推,那么数 K 就可以这样表示:

$$K=a[1]*1!+a[2]*2!+...+a[n]*n!$$

这是很好理解的,但是我们需要证明这是一种合法的进位方式,我们假设数 K 为该规则下的变进制数,它的第 a[i] 位为 i+1,现在我们需要进位。通过下等式,我们可以知道这么做是合法的。即进位后的数 K‘依旧满足该规则,且 K'=K+1.

$$a[i]*i!=(i+1)*i!=1*(i+1)!$$

同时这种变进制规则具有如下显然的性质:

  • (1) 当所有位 a[i] 均为 i 时,K 有最大值 (n+1)!-1
  • (2) 当所有位 a[i] 均为 0 时,K 有最小值 0

那么我们就得到了一种合法的,具有良好性质的变进制数辣!

逆序对


这貌似不需要说... 知道其概念即可,下面直接引用百度百科定义

设 A 为一个有 n 个数字的有序集 (n>1),其中所有数字各不相同。
如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j],则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对,也称作逆序数。

康拓展开


终于到这里啦~假设我们有 b[0],b[1]...b[n] 共 n+1 个互异的元素,这些元素存在某种排序关系使得 b[0]<b[1]...<b[n],对它们任意排列,就有了 (n+1)! 种排列,我们记某排列其中第 i(1 ≤ i ≤ n) 个元素与它前面的 i 个元素构成的逆序对的对数为 di(0 ≤ di ≤ i),这恰好是上述变进制数的每一位!因此,每个排列都可以按这种方式表示成一个 n 位变进制数 ~

并且,这样做还有一个很好的性质,那就是 n+1 个元素的全排列的每一个排列对应着一个不同的 n 位变进制数 。下面证明引用自 这里 :(日后可能自己写一下更加易于理解的证明...)

对于全排列的任意两个不同的排列 p0,p1,p2,...,pn(排列 P)和 q0,q1,q2,...,qn(排列 Q),从后往前查找第一个不相同的元素,分别记为 pi 和 qi(0 < i <= n)。
(1)如果 qi > pi,那么,
如果在排列 Q 中 qi 之前的元素 x 与 qi 构成逆序对,即有 x > qi,则在排列 P 中 pi 之前也有相同元素 x > pi(因为 x > qi 且 qi > pi),即在排列 P 中 pi 之前的元素 x 也与 pi 构成逆序对,所以 pi 的逆序数大于等于 qi 的逆序数。又 qi 与 pi 在排列 P 中构成 pi 的逆序对,所以 pi 的逆序数大于 qi 的逆序数。
(2)同理,如果 pi > qi,那么 qi 的逆序数大于 pi 的逆序数。
因此,由(1)和(2)知,排列 P 和排列 Q 对应的变进制数至少有第 i 位不相同,即全排列的任意两个不同的排列具有不同的变进制数。至此,定理 1 得证。

这样,全排列就可以映射到自然数空间啦~

这就是康托展开

应用


我们重复一遍原始公式便于查阅$$X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[1]*0!$$

如果你耐心的看完并理解了上述文字,那么代码的实现对你来说应该是不困难的,我们考虑当我们知道某排列时如何求它的排名:

若你看了上述文字,相信你已经知道 a[i] 是什么了,若没有,下面给出的信息对你来说可以当做结论来记忆理解.

a[i] 的含义即为第 i 位上的数所对应的逆序对个数,即上述 d[i]!

换一个角度,可以这样理解:

我们给出这样一个排列: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!.

明白了做法,那么代码实现就是显然的啦~我们枚举每一位的逆序对个数,套用公式即可~

代码将会在文章的最后随着逆康托展开一起给出

逆康拓展开


 

在前文说到康托展开是可逆的,因为它是无冲突的,所以当我们给出 n 和某名次 m 时,我们也可以得到 m 对应的排列是什么,我们的做法和康托展开正好相反,只有套用公式解出 d[i] 的值即可,我们的做法在求某一位 d[i] 时,对当前 X 除以 (n-i)!,这样商即是要求的 d[i],余数即是剩余项的和,直接进入下一步循环即可,但是在这里 (脑) (残) 的读 (博) (主) 可能会有一个小问题:如何保证上述做法的正确性呢?剩余项的和是否有可能大于等于当前项使得出现问题呢?自然,这是不可能的,下面博主给出 (需要感性理解的)(不严谨的)(愚蠢) 的证明:

我们思考构造一组当前项尽可能小,剩余项的和尽可能大的数据,显然,我们唯一可以控制的参数就是 d[i],我们不难构造出如下的排列:1,n,n-1,n-2,...2

对于该式,如果上述做法依旧成立,那么其余情况不可能比此更糟了,那么我们需要证明的便是:$$n!> \sum_{i=1}^{n}(n-i)*(n-i)!$$

将每一项 ( n-i ) * ( n-i ) ! 拆成$$( n-i+1) * (n-i)! - 1*(n-i) !$$

那么原式就可以整理得:$$( 1!+2!+3!+...+n! )-( 0!+1!+...+( n-1 )! ) = n!-1 < n!$$

该做法成立,证毕~

有了 d[i],想推出 a[i] 自然是很容易的啦~但是要注意,康托展开是对应 [0,(n-1)!] 间的自然数的,它包括 0,这意味着,我们通常意义上的从 1 开始的“名次”在进行逆康托展开前需要先-1...

下面给出代码:

例题


终于有了.... [USACO2011 Feb] Cow Line


一个蒟蒻oier的博客 |稍有常识的人都能看出,公告里已经说啦注册功能尚未恢复,不要再试啦~想要账号可以在任意一篇文章下评论留下联系方式或者私聊博主qq获取!~