Skip to content

第四章 生成排列组合

4.1 生成排列

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

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

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

算法 1

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

算法 2

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

1 从来不可移动

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

  • n\displaystyle{ n } 是第一个整数而它的箭头指向左边
  • n\displaystyle{ n } 是最后一个整数而它的箭头指向右边
  • 1,2,,n\displaystyle{ 1 ^{ \gets } , 2 ^{ \gets } , \ldots , n ^{ \gets } } 开始
  • 当存在可移动整数时
    • 求出最大可移动整数 m\displaystyle{ m }
    • 交换 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

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

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

4.2 排列中的逆序

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

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

逆序列

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

换句话说,aj\displaystyle{ a _{ j } } 代表在 ij\displaystyle{ i _{ j } } 这个数左边,有多少个比 ij\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

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

0b1n1,0b2n2,,0bn11,bn=0\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 }

那么一定存在唯一一个 {1,2,,n}\displaystyle{ \left\lbrace 1 , 2 , \ldots , n \right\rbrace } 的排列,其逆序列为 b1,,bn\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 生成组合

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

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

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

Gray 码

000
001
011
010
110
111
101
100

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

Gray 码后继

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

4.4 生成 r 子集

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

a1a2...ar\displaystyle{ a _{ 1 } a _{ 2. } .. a _{ r } } 1a1<a2<<arn\displaystyle{ 1 \leqslant a _{ 1 } < a _{ 2 } < \ldots < a _{ r } \leqslant n }

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

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

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

(nr)(na1r)(na2r1)(nar12)(nar1)\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 偏序和等价关系

离散数学

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

  1. 自反性
    • xA,x,xR\displaystyle{ \forall x \in A , \left\langle x , x \right\rangle \in R }
    • IAR\displaystyle{ I _{ A } \subseteq R }
    • 主对角线上都是 1 的矩阵
  2. 反自反性
    • xA,x,xR\displaystyle{ \forall x \in A , \left\langle x , x \right\rangle \notin R }
    • IAR=\displaystyle{ I _{ A } \cap R = \varnothing }
    • 主对角线上都是 0 的矩阵
  3. 对称性
    • x,yA,x,yRy,xR\displaystyle{ \forall x , y \in A , \left\langle x , y \right\rangle \in R \to \left\langle y , x \right\rangle \in R }
    • R=R1\displaystyle{ R = R ^{ {-1 } } }
    • 对称矩阵
  4. 反对称性
    • x,yA,x,yRy,xRx=y\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 }
    • RR1IA\displaystyle{ R \cap R ^{ {-1 } } \subseteq I _{ A } }
    • 当矩阵中 ij\displaystyle{ i \ne j }A[i,j]=1\displaystyle{ A \left[ i , j \right] = 1 }A[j,i]\displaystyle{ A \left[ j , i \right] } 必须为 0
  5. 传递性
    • x,y,zA,x,yRy,zRx,zR\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 }
    • R=RR2R3\displaystyle{ R = R \cup R ^{ 2 } \cup R ^{ 3 } \cup \ldots }

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

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

定理 4.5.1

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