中介数

前面介绍了各种全排列算法，那么有这样一些问题：

• 给定一个排列，求它之前或之后的第 \(k\) 个排列
• 给定一个排列，求它的序号
• 给定一个序号，求排列

我们知道，对于 \(n\) 个数，有 \(n!\) 种排列方式。每种算法生成的排列顺序是不一样的， 这个在前文中有一个颜色图能直观看出来。

我们将这些排列从 \(0\) 到 \((n!-1)\) 右边比它小的数的个数。 编号，这样每个排列就有了自己的序号。¹

单纯从序号，我们比较难直接推导出排列本身，这样就需要引入中介数 的概念。

定义 #

中介数是为了快速推导某个排列的中间数。

以字典序为例，

假设排列 \(\sigma = (\sigma_0,\sigma_1,…\sigma_{n-1})\)，定义中介数为 \(L(\sigma) = (L_0,L_1,…L_{n-1})\)，其中 \(L_i\) 表示 \(\sigma_i\) 右边比它的小的数的个数。

以 \(\sigma = (83674521)\) 为例，它的中介数是 \(L = (7244221)\)。 因为最后一位的右边没有数字，那么 \(L_{n-1}\) 总是 0，可以省略，所以中介数比原排列少一位。

• 中介数是特殊进制设计，最低位是 1 进制 \((L_{n-1})\)，次低位是 2 进制，依次类推
• 中介数的计算：

\(L(\sigma) = L_{n-2} * 1! + … + L_0 * (n-1)! = \displaystyle\sum_{i=0}^{n-2}L_i * (n-1-i)! \)

这个十进制结果就是字典序的序号

• 一个 \(n-1\) 位的中介数，可以表示 \(n!\) 个数字，正好与排列数对应
• 一个中介数对应一个特定的排列，同样根据一个排列也能求出其中介数

字典序的中介数也叫 Lehmer Code - 莱默编码²

应用 #

60. Permutation Sequence

1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

有了中介数的定义，我们来解决两个基本问题：

中介数 <-> 序号 #

1. 中介数 -> 序号

这个直接使用上面的公式 \(\displaystyle\sum_{i=0}^{n-2}L_i * (n-1-i)! \) 即可

override func code_to_index() {
    index = 0
    var factorial = 1
    for i in (0..<sz-1).reversed() {
        index += L[i] * factorial
        factorial *= (sz-i)
    }
}

2. 序号 -> 中介数

我们观察一下求和公式：

\(L(\sigma) = L_{n-2} * 1! + … + L_0 * (n-1)! = L_{n-2} + L_{n-3} * 2 + L_{n-4} * 3 * 2 + … + L_0 * (n-1) * (n-2) * … * 2\)

首先 \(L_{n-2}\) 是整个和除 \(2\) 的余数，然后 \(L_{n-3}\) 是除 \(2\) 的商，再除 \(3\) 的余数，依次类推。

override func index_to_code() {
    var tmp = index
    for i in (0..<sz-1).reversed() {
        L[i] = tmp % (sz - i)
        tmp /= (sz - i)
    }
}

中介数 <-> 排列 #

1. 排列 -> 中介数

这个比较简单，按照定义求解即可。

override func order_to_code() {
    for i in 0..<sz-1 {
        var cnt = 0
        for j in i+1..<sz {
            if nums[j] < nums[i] {
                cnt += 1
            }
        }
        L[i] = cnt
    }
}

2. 中介数 -> 排列

从 \(L_0\) 开始，它表示排列的第一位右边比它的小的数的个数，很明显排列第一位就是 \(L_0 + 1\)，但是到第二位的时候， 可能不是 \(L_1 + 1\)，因为如果 \(L_0 + 1\) 如果比它小，就应该是 \(L_1 + 2\)。

这样说可能不太容易理解，还是以 \(\sigma = (83674521)\) 为例，如果中介数是 \(L = (7244221)\)， 第一位是 \(7 + 1 = 8\) ，第二位是 \(2 + 1 = 3\)，到第三位时，由于前面出现了 \(3\)，比 \(4 + 1 = 5\) 要小， 那么计数就应该 \(+1\)，所以第三位是 \(6\)。

override func code_to_order() {
    nums = L.map({ $0 + 1 })
    for i in stride(from: sz-1, to: 0, by: -1) {
        for j in stride(from: i - 1, to: -1, by: -1) {
            if (nums[j] <= nums[i]) {
                nums[i] += 1
            }
        }
    }
}

解决了这两个互相转换的问题，我们就可以以 中介数 为桥梁，解决 排列 与 序号 间的转换。 这也是 中介数 这个词的本来意义。

那么，这个 Hard 问题 60. Permutation Sequence 就可以变成：

index_to_code()
code_to_order()

不同算法的中介数 #

不同的算法中的中介数定义是不一样的，下面再说明一下另外几种常见排列算法的 中介数 定义。

假设排列 \(\sigma = (\sigma_0,\sigma_1,…\sigma_{n-1})\)

为了方便做加法，我们把中介数的最低位放在 \(L_0\)，这样与一般表示出来的是相反的。

以 \((83674521)\) 为例，递增中介数是 \((7442221)\)，存储在数据组中是 \([1, 2, 2, 2, 4, 4, 7]\)。

递增进位法 #

定义 \(L(\sigma) = (L_1,L_2,..L_{n-1})\)，其中 \(L_i\) 表示 \((i+1)\) 右边比它小的数的个数。

由于 \(L_0 = 0\)，所以这一位通常被忽略。

那么，它的范围就是 \((0,0,..,0) \thicksim (1,2,3,..{n-1})\)，注意 \(L_i\) 是 \(i+1\) 进制数。

递减进位法 #

定义 \(L(\sigma) = (L_0,L_1,..L_{n-2})\)，其中 \(L_i\) 表示 \((n-i)\) 右边比它小的数的个数。

由于 \(L_{n-1} = 0\)，所以这一位也是被忽略的。

那么，它的范围就是 \((0,0,..,0) \thicksim ({n-1},{n-2},..1)\)，注意 \(L_i\) 是 \(n-i\) 进制数。

可以看出来，递增和递减进位法的中介数的位数都是 \(n-1\) 个。

邻位对换法 #

定义 \(L(\sigma) = (L_0,L_1,..L_{n-2})\)，其中 \(L_i\) 表示 \((n-i)\) 的 方向的反方向 上比它小的数的个数。其中 \(L_{n-1} = 0\)，这一位也是被忽略的。

邻位交换法的中介数是比较难理解的。有几个重要的概念^{3 4}：

1. 逆序：对于一个序列中的两个元素 \(\sigma_i, \sigma_j\)，如果 \(i < j\) 的同时，\(\sigma_i > \sigma_j\)，则称 \((i, j)\) 是一个逆序。
2. 逆序数：一个序列中任意两个元素两两组合，它们是逆序的的个数称为逆序数。
3. 逆序数为偶数的排列称为偶排列，反之为奇排列。

这样，初始的递增排列，逆序数为 \(0\)，是偶排列。

另外一个概念是 方向，下面是几条规则：

1. 排列中一个数的方向由比它小的数的构成的序列的逆序数决定，逆序数为偶数时，向左；否则向右。
2. 逆序数的奇偶性与它的中介数对应的序号的奇偶性一致。
3. 由于中介数是最大数到最小数排列的，那么比它小的数组成排列的中介数，就是当前位后面的中介数。

完整的实现代码在 Gist 上

练习 #

求不同的排列算法中 83674521 之前第 2015 个排列。⁵

这个问题的求解步骤是：

原排列 -> 原中介数 -> 序号 -> 减去 2015 -> 新序号 -> 新中介数 -> 新排列

还有一种方式是：

原排列 -> 原中介数 -> 减去 2015 的中介数 -> 新中介数 -> 新排列

后一种方式，需要计算 2015 在不同算法中的中介数，同时减法也是在特殊进制下求解，会比较麻烦。 所以，把中介数转成十进制的序号，直接计算会比较方便一点。

通过计算，我们得出四种不同算法的结果：