生成排列和组合¶

生成排列¶

Stirling公式: $$ n! = \sqrt{2 \pi n}(\frac{n}{e})^n $$ 给定一个整数 $k$ ，赋予其一个方向得 $\overrightarrow{k}$ 或 $\overleftarrow{k}$，如果一个整数指向的相邻数比它要小，则这个整数是可移动的

生成 $\{1, 2, \cdots, n\}$ 的排列的算法: 从 $\overleftarrow{1} \overleftarrow{2} \cdots \overleftarrow{n}$ 开始，当存在可移动整数时，

找出最大的可移动整数 $m$
交换 $m$ 和它指向的相邻整数
交换所有满足 $p > m$ 的整数 $p$ 的箭头方向

《组合数学》P56

排列中的逆序¶

设 $i_1 i_2 \cdots i_n$ 是 $\{1, 2, \cdots, n\}$ 的一个排列，如果 $k < l$ 且 $i_k > i_l$ ，则称数对 $(i_k, i_l)$ 为一个逆序 (inversion)

令 $a_j$ 为排列中在 $j$ 前又大于 $j$ 的整数个数

数值序列 $a_1, a_2, \cdots, a_n$ 叫做排列 $i_1 i_2 \cdots i_n$ 的逆序列。例如: 31524 的逆序列是 1,2,0,1,0

定理 设 $b_1, b_2, \cdots, b_n$ 是满足以下条件的整数序列: $$ 0 \leqslant b_1 \leqslant n-1, 0 \leqslant b_2 \leqslant n-2, \cdots, 0 \leqslant b_{n-1} \leqslant 1, b_n = 0 $$ 那么，一定存在唯一一个 $\{1, 2, \cdots, n\}$ 的排列，它的逆序列是 $b_1, b_2, \cdots, b_n$

证明思路: 找出唯一的排列即可

按照逆序个数的奇偶性把一个排列称为奇排列或偶排列

生成组合¶

取 $S = \{x_{n-1}, \cdots, x_1, x_0\}$，想将 $S$ 的所有子集列出

对应二进制数 $\Rightarrow$ 字典序/压缩序
Gray码

Gray码定义¶

生成Gray码相当于沿着 $n$ 方体的边遍历该 $n$ 方体，经过每个角点恰好一次

二阶Gray生成三阶Gray: “投影”到后边再补1。通过这种方式构建的Gray码叫反射Gray码

递归定义:

生成Gray码的算法¶

以反射Gray码的顺序生成 $0,1$ 的 $n$ 元组的算法:

若 $a_{n-1}a_{n-2}\cdots a_0$ 是 $0$ 和 $1$ 的 $n$ 元组，则 $\sigma(a_{n-1}a_{n-2}\cdots a_0) = a_{n-1} + a_{n-2} + \cdots + a_0$ 是其中 $1$ 的个数

证明 证明这个算法确实产生的是反射Gray码

$n = 1$ 时，显然成立
设 $n>1$ 且对于 $n-1$ 这个算法产生 $n-1$ 阶反射Gray码
Gray码的前 $2^{n-1}$ 是在所有数前补0，而算法生成的前 $2^{n-1}$ 个也是一样的（0不影响）
Gray码的后半部分，假设有 $$ 1a_{n-2}\cdots a_0 $$

\[ 1b_{n-2}\cdots b_0 \]

说明 $n-1$ 阶Gray码有 $$ b_{n-2}\cdots b_0 $$

\[ a_{n-2}\cdots a_{0} \]

$\sigma(a_{n-2}\cdots a_0)$ 和 $\sigma(b_{n-2}\cdots b_0)$ 的奇偶性相反，$\sigma(1a_{n-2}\cdots a_0)$ 和 $\sigma(a_{n-2}\cdots a_0)$ 的奇偶性也相反。假设 $\sigma(b_{n-2}\cdots b_0)$ 为偶，则通过改变 $b_0$ 得到 $a_0$ ，算法中将把 $1a_{n-2}\cdots a_0$ 中的 $a_0$ 修改；假设 $\sigma(b_{n-2}\cdots b_0)$ 为奇……

思考: 给出一个Gray码，问它是Gray码表中的第几个？

生成 $r$ 子集¶

我们想让所有 $r$ 子集按一定顺序出现，先定义集合的字典序: 两个集合 $A$ 和 $B$ ，只在两集合中的一个的最小整数在 $A$ 中，则称在字典序中 $A$ 先于 $B$ (为了便于观察，把子集中的元素按从小到大的顺序写)

找直接后继的方法:

确定某一子集的位置:

证明 先计算出现在 $a_1a_2\cdots a_r$ 后面的 $r$ 子集的数目:

在 $a_1a_2\cdots a_r$ 后且第1个元素比 $a_1$ 大的子集有 $\binom{n-a_1}{r}$ (只选 $r$ 个比 $a_1$ 大的数即可)
在 $a_1a_2\cdots a_r$ 后且第1个元素是 $a_1$ 但第二个元素大于 $a_2$ 的子集有 $\binom{n-a_2}{r-1}$
……