第四章 生成排列组合

4.1 生成排列

由钱 $\displaystyle{ n }$ 个正整数组成的集合 $\displaystyle{ \left\lbrace 1 , 2 , \ldots , n \right\rbrace 有 }$n!$ 个排列

$$\displaystyle{ {n !} \sim \sqrt{ 2 \pi n } \left( \frac{ n }{ e } \right) ^{ n } }$$

目标：简单优美地生成 $\displaystyle{ \left\lbrace 1 , 2 , \ldots , n \right\rbrace }$ 所有排列的算法。

算法 1

给定 $\displaystyle{ \left\lbrace 1 , 2 , \ldots , n - 1 \right\rbrace }$ 的 $\displaystyle{ {\left( n - 1 \right) !} }$ 个排列的表，能够通过以所有可能的方式，系统地将 $\displaystyle{ n }$ 插入到 $\displaystyle{ \left\lbrace 1 , 2 , \ldots , n - 1 \right\rbrace }$ 的每个排列中，得到 $\displaystyle{ {n !} }$ 个排列的表。

算法 2

定义如果一个整数 $\displaystyle{ k }$ 的箭头指向一个与其相邻但比它小的整数，那么称这个 $\displaystyle{ k }$ 是可移动的。

1 从来不可移动

除了下面两种情形外，$\displaystyle{ n }$ 总是可以移动的

• $\displaystyle{ n }$ 是第一个整数而它的箭头指向左边
• $\displaystyle{ n }$ 是最后一个整数而它的箭头指向右边

• 从 $\displaystyle{ 1 ^{ \gets } , 2 ^{ \gets } , \ldots , n ^{ \gets } }$ 开始
• 当存在可移动整数时
  • 求出最大可移动整数 $\displaystyle{ m }$
  • 交换 $\displaystyle{ m }$ 和它的箭头

 1  1l 2l 3l 4l   4
 2  1l 2l 4l 3l   4
 3  1l 4l 2l 3l   4
 4  4l 1l 2l 3l   3
 5  4r 1l 3l 2l   4
 6  1l 4r 3l 2l   4
 7  1l 3l 4r 2l   4
 8  1l 3l 2l 4r   3
 9  3l 1l 2l 4l   4
10  3l 1l 4l 2l   4
11  3l 4l 1l 2l   4
12  4l 3l 1l 2l   2
13  4r 3r 2l 1l   4
14  3r 4r 2l 1l   4
15  3r 2l 4r 1l   4
16  3r 2l 1l 4r   3
17  2l 3r 1l 4l   4
18  2l 3r 4l 1l   4
19  2l 4l 3r 1l   4
20  4l 2l 3r 1l   3
21  4r 2l 1l 3r   4
22  2l 4r 1l 3r   4
23  2l 1l 4r 3r   4
24  2l 1l 3r 4r   end

生成 $\displaystyle{ \left\lbrace 1 , 2 , \ldots , n \right\rbrace }$ 的随机排列：使用某种方法生成一个排列，使得这 $\displaystyle{ {n !} }$ 个开裂中每个排列被生成的概率都为 $\displaystyle{ \frac{ 1 }{ {n !} } }$

Knuth shuffle 方法：从一个更等排列 $\displaystyle{ 1 , 2 , \ldots , n }$ 开始，对于 $\displaystyle{ 1 , 2 , \ldots , n - 1 }$ 中的每一个整数，连续随机地从 $\displaystyle{ k , k + 1 , \ldots , n }$ 个位置中为它们选定一个位置，并把位置 $\displaystyle{ k }$ 上的整数与被训吖啶的位置交换。

4.2 排列中的逆序

设 $\displaystyle{ i _{ 1 } , i _{ 2 } , \ldots , i _{ n } }$ 是集合 1~n 的一个排列，如果 $\displaystyle{ k < l }$ 且 $\displaystyle{ i _{ k } > i _{ l } }$， 则称数对 $\displaystyle{ \left( i _{ k } , i _{ l } \right) }$ 为一个逆序。

排列 31524 有 4 个逆序对，分别为 (3, 1), (3, 2), (5, 2), (5, 4)

逆序列

对于一个排列 $\displaystyle{ i _{ 1 } , i _{ 2 } , \ldots , i _{ n } }$，其逆序列 $\displaystyle{ a _{ 1 } a _{ 2. } .. a _{ n } }$，其中 $\displaystyle{ a _{ j } }$ 标识第二个成分是 $\displaystyle{ j }$ 的逆序的数量。

换句话说，$\displaystyle{ a _{ j } }$ 代表在 $\displaystyle{ i _{ j } }$ 这个数左边，有多少个比 $\displaystyle{ i _{ j } }$ 大的数。

31524 的逆序列为 1, 2, 0, 1, 0

• 1 的左边有 1 个比 1 大的数字——3
• 2 左边有 2 个比 2 大的数字——3, 5
• 3 左边没有比 3 大的数字
• 4 左边有 1 个比 4 大的数字——5
• 5 左边没有比 5 大的数字

从逆序列可以唯一构建一个排列

定理 4.2.1

设 $\displaystyle{ b _{ 1 } , \ldots , b _{ n } }$ 是满足下面条件的整数序列

$$\displaystyle{ 0 \leqslant b _{ 1 } \leqslant n - 1 , 0 \leqslant b _{ 2 } \leqslant n - 2 , \ldots , 0 \leqslant b _{ n - 1 } \leqslant 1 , b _{ n } = 0 }$$

那么一定存在唯一一个 $\displaystyle{ \left\lbrace 1 , 2 , \ldots , n \right\rbrace }$ 的排列，其逆序列为 $\displaystyle{ b _{ 1 } , \ldots , b _{ n } }$

逆序列构建原排列

假设逆序列为 5, 3, 4, 0, 2, 1, 1, 0

_ _ _ _ _ 1 _ _
_ _ _ 2 _ 1 _ _
_ _ _ 2 _ 1 3 _
4 _ _ 2 _ 1 3 _
4 _ _ 2 5 1 3 _
4 _ 6 2 5 1 3 _
4 _ 6 2 5 1 3 7
4 8 6 2 5 1 3 7

4.3 生成组合

$\displaystyle{ n }$ 元集合 $\displaystyle{ S _{ n } }$ 中选组合，把它的 $\displaystyle{ 2 ^{ n } }$ 个子集看成 $\displaystyle{ 2 ^{ n } }$ 个 0 和 1 的组合。

生成所有的 $\displaystyle{ 2 ^{ n } }$ 个子集：将 $\displaystyle{ 2 ^{ n } }$ 用二进制按顺序写，取位数为 1 的那个元素。该顺序被称为“字典序”。

生成时使相邻子集差异尽可能小

Gray 码

000
001
011
010
110
111
101
100

Gray 码生成方式：比如现在生成了 $\displaystyle{ 2 ^{ k } }$ 个 Gray 码，那么将上面的 Gray 码逆序抄下来，然后将抄下来的 $\displaystyle{ 2 ^{ k } }$ 个 Gray 码的第 $\displaystyle{ k }$ 位（从右 0 开始数）更改为 1

Gray 码后继

1. 如果 1 的数量为偶数，则更改翻转最右一位
2. 如果 1 的数量为奇数，则从右找第一个 1，翻转它左边的一位

4.4 生成 r 子集

从 $\displaystyle{ S = \left\lbrace 1 , 2 , \ldots , n \right\rbrace }$ 中选出一个 $\displaystyle{ r }$ 子集，生成所有的 $\displaystyle{ r }$ 子集

$$\displaystyle{ a _{ 1 } a _{ 2. } .. a _{ r } }$$ $$\displaystyle{ 1 \leqslant a _{ 1 } < a _{ 2 } < \ldots < a _{ r } \leqslant n }$$

最后一个 $\displaystyle{ r }$ 子集为 $\displaystyle{ \left\lbrace n - r + 1 , n - r + 2 , \ldots , n \right\rbrace }$

找后继：找到一个 $\displaystyle{ a _{ k } < n }$ 使得 $\displaystyle{ a _{ k } + 1 }$ 不等于 $\displaystyle{ a _{ k + 1 } , \ldots , a _{ n } }$ 中的任意一个，将 $\displaystyle{ a _{ k } }$ 加一，后续依次加一，构成序列

找绝对位置：子集 $\displaystyle{ \left\lbrace a _{ 1 } , a _{ 2 } , \ldots , a _{ r } \right\rbrace }$ 出现的位置为

$$\displaystyle{ { n \choose r } - { n - a _{ 1 } \choose r } - { n - a _{ 2 } \choose r - 1 } - \ldots - { n - a _{ r - 1 } \choose 2 } - { n - a _{ r } \choose 1 } }$$

4.5 偏序和等价关系

离散数学

给定 $\displaystyle{ R }$ 是 $\displaystyle{ A }$ 上的二元关系

1. 自反性
   • $\displaystyle{ \forall x \in A , \left\langle x , x \right\rangle \in R }$
   • $\displaystyle{ I _{ A } \subseteq R }$
   • 主对角线上都是 1 的矩阵
2. 反自反性
   • $\displaystyle{ \forall x \in A , \left\langle x , x \right\rangle \notin R }$
   • $\displaystyle{ I _{ A } \cap R = \varnothing }$
   • 主对角线上都是 0 的矩阵
3. 对称性
   • $\displaystyle{ \forall x , y \in A , \left\langle x , y \right\rangle \in R \to \left\langle y , x \right\rangle \in R }$
   • $\displaystyle{ R = R ^{ {-1 } } }$
   • 对称矩阵
4. 反对称性
   • $\displaystyle{ \forall x , y \in A , \left\langle x , y \right\rangle \in R \wedge \left\langle y , x \right\rangle \in R \to x = y }$
   • $\displaystyle{ R \cap R ^{ {-1 } } \subseteq I _{ A } }$
   • 当矩阵中 $\displaystyle{ i \ne j }$ 且 $\displaystyle{ A \left[ i , j \right] = 1 }$ 则 $\displaystyle{ A \left[ j , i \right] }$ 必须为 0
5. 传递性
   • $\displaystyle{ \forall x , y , z \in A , \left\langle x , y \right\rangle \in R \wedge \left\langle y , z \right\rangle \in R \to \left\langle x , z \right\rangle \in R }$
   • $\displaystyle{ R = R \cup R ^{ 2 } \cup R ^{ 3 } \cup \ldots }$

存在一些事件既不是对称的，也不是反对称的

• 等价关系满足 1, 3, 5，例如“同奇偶”
• 偏序关系满足 1, 4, 5，例如“大于等于”，“整除”
  • $\displaystyle{ x \preceq y }$

定理 4.5.1

设 $\displaystyle{ X }$ 是有 $\displaystyle{ n }$ 个元素的有限集合，则 $\displaystyle{ X }$ 上的全序与 $\displaystyle{ X }$ 的排列之间存在一一对应。特别的，$\displaystyle{ X }$ 上不同全序的个数为 $\displaystyle{ {n !} }$