康托展开的编码、解码和全排列

对于不重复的 $n$ 个数，其有 $n!$ 个排列。如果我们要求其中第 $k$ 个排列，可以通过构造一个全排列到自然数 $\left[0, n!\right)$ 的双射来直接构造这个排列。

康托展开就是这样一个映射。康托展开不在意数的具体数值，只在乎其全序顺位，即在集合中排序到第几小；或者说有多少数比此数更小。

理论部分

对于这样一个排列（注意下标方向） $$\left\{k_n, k_{n-1}, \cdots, k_1\right\}$$ 我们可以构造这样一个数列 $\left\{a_i\right\}_{i=1}^n$，定义为 $k_i$ 右侧 比 $k_i$ 更小的数。${a_i}$ 实际上是 Lehmer code，可以用如下公式描述： $$a_i=\#\left\{i>j:k_i>k_j\right\}$$ 显然，我们有 $$0 \le a_i \lt i\tag{1}$$ 容易发现，对于不存在重复元素、存在全序关系的集合，$\{a_i\}$ 和 $\{k_i\}$ 构成双射。那么，只要我们实现 $\{a_i\}$ 到区间 $\left[0, n!\right)$ 的双射，就完成了从 ${k_i}$ 到自然数的双射。

定义映射 $$X=\sum\limits_{i=1}^n {a_i \left(i-1\right)!} \tag{2}$$ 由式 $(1)$ ，$X$ 的取值范围正为 $\left[0, n!\right)$ 。又由于 $a_i(i-1)!$ 严格大于 $a_{i-1}(i-2)!$，因此存在 $X$ 到 $a_i$ 的双射。这就是康托展开（康托编码）。

解释

这里我不会严谨证明公式 $(2)$，但是我们可以感性地理解这个公式：

对于第 $i$ 位数字，只考虑其及其右边的部分排列。我们来考虑有多少种排列比当前排列的序数小。

第 $i$ 位数字右侧有 $a_i$ 位比它小的数字，代表任取这 $a_i$ 个数字中任意一个与 $k_i$ 交换位置，都只会得到比当前排列更小的排列序数（字典序）。因此，不妨随意取一个，考虑这样交换后会获得多少种排列？

显然，其右侧有 $i-1$ 位数字，构成 $(i-1)!$ 种排列。

因此，对于第 $i$ 位数字，我们可以找到 $a_i (i-1)!$ 种排列的序数比其小。

注意到我们只是考虑了 $i$ 位对应的 $a_i$ ，其后具体的排列并没有引入这里，因此可以对其右侧继续进行这样的计算并累加到最终结果。最终，就可以得到公式 $(2)$。

例子

对于集合 ${1,2,3}$，考虑其排列和上面的定义，可以得到这样的表，加强理解：

排列	123	132	213	231	312	321
序数	1	2	3	4	5	6
$a_i$	000	010	100	110	200	210
$(i-1)!$	210	210	210	210	210	210
$X$	$0$	$1*1=1$	$2*1=2$	$3$	$4$	$5$

算法实现

正向

def cantor_expansion(k: List[int]) -> int:
    result: int = 0
    factorial: int = 1
    N: int = len(k)
    for i in range(N-1, -1, -1):  # from end to begin
        a_i = sum(k[i] > k[j] for j in range(i+1, N))
        result += a_i * factorial
        factorial *= (N - i)
    return result

逆向

def cantor_expansion_reverse(index: int, N: int) -> List[int]:
    permutation = [None] * N
    for i in range(1, N+1):
        permutation[N - i] = index % i  # a_i
        index //= i
    # convert a_i to k_i
    options = list(range(N))
    for i in range(N):
        a_i = permutation[i]
        permutation[i] = options.pop(a_i)
    return permutation

测试验证

from itertools import permutations
N = 5
for index, perm in enumerate(permutations(range(N))):
    assert cantor_expansion(perm) == index
    assert list(perm) == cantor_expansion_reverse(index, N)

算法复杂度

正向

这里的算法是 $O(n^2)$ 的，如果维护前缀和可以优化到 $O(n \log n)$。

逆向

算法需要进行 $n$ 次选择当前选项中第 $a_i$ 小的数字。这里简单用 list 可以实现 $O(n^2)$ 复杂度算法。如果用平衡树/线段树，可以实现 $O(n \log n)$ 复杂度。

应用

对于 LeetCode #60，

给出集合 [1,2,3,…,n]，其所有元素共有 $n!$ 种排列。

给定 $n$ 和 $k$，返回第 $k$ 个排列。

我们可以这样解决：

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        return ''.join(
            str(i+1) for i in
            cantor_expansion_reverse(k-1, n))