Skip to main content
Ryder Fang ᝰ

中介数

·561 words·3 mins· 👀

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

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

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

我们将这些排列从 \(0\) 到 \((n!-1)\) 右边比它小的数的个数。 编号,这样每个排列就有了自己的序号。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 - 莱默编码2

应用 #

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)
    }
}
  1. 序号 -> 中介数

我们观察一下求和公式:

\(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
    }
}
  1. 中介数 -> 排列

从 \(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 个排列。5

这个问题的求解步骤是:

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

还有一种方式是:

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

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

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

算法原排列原中介数原序号新序号新中介数新排列
字典序836745217244221037313352987000300081237456
递增进位法8367452174422213870536690715330086451273
递减进位法8367452112224473789535880121145037624518
邻位交换法8367452110121202258420569100112148673251