第四章第四章 生成排列和组合生成排列和组合4.1 生成排列生成排列 算法一算法一: (生成集合生成集合1,2,n的的 n!个排列个排列) 基本思想是递归地对集合基本思想是递归地对集合1,2,n-1的的(n-1)!个排列的每一个排列个排列的每一个排列, 通过把通过把 n 插入到首、插入到首、 尾和任两个数的中间共尾和任两个数的中间共 n 个位置，产生集合个位置，产生集合1,2,n的的 n 个排列，从而产生个排列，从而产生 n (n-1)!=n!个个 集合集合1,2,n的排列。的排列。算例：算例：排列排列 n=1: 1n=2: 1 22 1n=3: 1 2 3 1 3 23 1 23 2 12 3 12 1 3n=4:1 2 3 41 2 4 31 4 2 34 1 2 34 1 3 21 4 3 21 3 4 21 3 2 43 1 2 43 1 4 23 4 1 24 3 1 24 3 2 13 4 2 13 2 4 13 2 1 42 3 1 42 3 4 1 2 4 3 1 4 2 3 1 4 2 1 3 2 4 1 3 2 1 4 3 2 1 3 4n=5: 、 、 、 算法结束，生成全部排列。算法结束，生成全部排列。算法二算法二: (生成集合生成集合1,2,n的的 n!个排列个排列)定义定义:对任一给定整数对任一给定整数 k, 其上加一个箭头表示移动方向其上加一个箭头表示移动方向,或或. 对于集合对于集合1,2,n的任一的任一kr ks个排列个排列,其中每一个整数都有一个箭头指出其移动方向其中每一个整数都有一个箭头指出其移动方向, 若整数若整数 k 的箭头指向与其相邻但的箭头指向与其相邻但 比它小的整数比它小的整数, 称称 k 是活动的是活动的.算法算法:从从开始开始, 当不存在活动的整数时当不存在活动的整数时,算法结束算法结束. 1s2s3sns(1)求出最大的活动整数求出最大的活动整数 m; (2)交换交换 m 和它箭头所指的相邻数和它箭头所指的相邻数; (3)改变所有满足改变所有满足 pm 的整数的整数 p 的方向的方向.算例算例: (n=4)4.2 排列中的逆序排列中的逆序定义：定义： 令令 i1 i2 in 是集合是集合1,2,n的一个排列，如果的一个排列，如果 0 k iL , 称数对（称数对（ik ，iL）是排列的一个逆序。）是排列的一个逆序。例：例：31524 的逆序的逆序定义：定义：令令 aj表示排列表示排列 i1 i2 in中数中数 j 的逆序数，称的逆序数，称 a1, a2, an为排列为排列 i1 i2 in 的逆序列。的逆序列。例：排列例：排列 31524 的逆序列的逆序列逆序列的性质：逆序列的性质： (1) 0 a1 n-1, 0 a2 n-2, , 0 an-1 1, an =0。(2) 逆序列数有逆序列数有 n!个。个。定理定理 4.2.1: 令令 b1, b2, bn为满足为满足0 b1 n-1, 0 b2 n-2, , 0 bn-1 1, bn =0 的整数序列，那么存在集合的整数序列，那么存在集合1,2,n的唯一一个排列，使它的逆序列为的唯一一个排列，使它的逆序列为 b1, b2, bn 。证明：（构造性证明）证明：（构造性证明）算法一：算法一：n:写出整数写出整数 nn-1:考虑考虑 bn-1，若，若 bn-1 =0，则，则 n-1 必在必在 n 的前面。的前面。若若 bn-1 =1：则：则 n-1 必在必在 n 的后面。的后面。n-2:考虑考虑 bn-2，若，若 bn-2 =0，则，则 n-2 必在上一步得到的排列的前面。必在上一步得到的排列的前面。若若 bn-2 =1，则，则 n-2 必在上一步得到的排列的两个数中间。必在上一步得到的排列的两个数中间。若若 bn-2 =2，则，则 n-2 必在上一步得到的排列的后面。必在上一步得到的排列的后面。1: 考虑考虑 b1，把，把 1 放在上一步得到的排列的第放在上一步得到的排列的第 b1 个数的后面。个数的后面。由算法可知，从由算法可知，从 n, n-1,2,1 每一步都根据每一步都根据 b1, b2, bn 唯一地确定唯一地确定 1,2,n 在排列中的位在排列中的位 置，两者存在一一对应关系。置，两者存在一一对应关系。算法二：算法二： 设有设有 n 个位置，标志为个位置，标志为 1,2,n 1:把把 1 放在放在 b1+1 位置上；位置上；2:把把 2 放在第放在第 b2+1 个个 空空 位置上；位置上；k: 把把 k 放在第放在第 bk+1 个个 空空 位置上；位置上；n: 把把 k 放在余下的放在余下的 空空 位置上；位置上；由算法可知，根据由算法可知，根据 b1, b2, bn 唯一地确定唯一地确定 1,2,n 在排列中的位置，两者存在一一对应关在排列中的位置，两者存在一一对应关 系。系。例例 1： 已知已知1,2,8的一个排列的逆序列为：的一个排列的逆序列为：5，3，4，0，2，1，1，0，确定此排列。，确定此排列。4.3 生成组合生成组合 令集合令集合 S=xn-1, xn-2, x-1, x0 ，生成，生成 S 的所有的所有 2n个组合。个组合。算法：算法： 从从 n 元组元组 an-1an-2a1a0=000 开始开始, 当当 an-1an-2a1a0=111 时算法结束时算法结束, 做做: (1)求出使得求出使得 aj=0 的最小整数的最小整数 j; (2)用用 1 代替代替 aj , 并且用并且用 0 代替代替 aj-1, aj-2 , , a0 . 算法正确性证明算法正确性证明:几种不同的组合输出序几种不同的组合输出序: (1)字典序字典序 (2)组合压缩序组合压缩序 (3)格雷格雷(Gray)码序码序n 阶反射格雷阶反射格雷(Gray)码的递归定义码的递归定义:(1) 1 阶反射格雷阶反射格雷(Gray)码是码是 ; 10(2) 设设 n1, 且且 n-1 阶反射格雷阶反射格雷(Gray)码已经构造好码已经构造好,首先顺序列出首先顺序列出 n-1 阶反射格雷阶反射格雷(Gray) 码的全部码的全部 n-1 元组元组, 并把并把 0 加到全部加到全部 n-1 元组的开头元组的开头; 然后再反序列出然后再反序列出 n-1 阶反射格雷阶反射格雷 (Gray)码的全部码的全部 n-1 元组元组, 并把并把 1 加到全部加到全部 n-1 元组的开头元组的开头.定义定义: 设设 an-1an-2a1a0是是 01 的的 n 元组元组, 定义定义函数为函数为: ( an-1an-2a1a0)= an-1+an-2+a0算法算法: (以反射格雷以反射格雷(Gray)码序生成全部码序生成全部 01 的的 n 元组元组)从从 n 元组元组 an-1an-2a1a0=000 开始开始, 当当 an-1an-2a1a0=100 时算法结束时算法结束, 做做: (1)计算计算( an-1an-2a1a0)= an-1+an-2+a0 (2)若若( an-1an-2a1a0)是偶数是偶数, 则改变则改变 a0(01 或或 10) (3) 若若( an-1an-2a1a0)是奇数是奇数, 确定这样的确定这样的 j, 使得对所有使得对所有 ij, 有有 ai=0. 改变改变 aj+1(01 或或 10).例例 1： 生成生成 4 阶反射格雷阶反射格雷(Gray)码码.定理定理 4.3.1(算法正确性证明算法正确性证明) 上述算法产生上述算法产生 n 阶反射格雷阶反射格雷(Gray)码码.例例 2： 在在 8 阶反射反射格雷阶反射反射格雷(Gray)码中码中,求求 10100110 的后继的后继,00011101 的前驱的前驱.4.4 生成生成 r 组合组合定理定理 4.41: 令令 a1a2ar是是1,2,n的一个的一个 r-组合组合, 在字典序中在字典序中, 第一个第一个 r-组合是组合是 12r, 最后一个最后一个 r-组合是组合是(n-r+1) (n-r+2)n, 设设 a1a2ar (n-r+1) (n-r+2)n, 令令 k 是满足是满足 akn 且使得且使得 ak+1 不同于不同于 a1, a2,ar 中任一数的最大整数中任一数的最大整数, 那么那么, 在字典序中在字典序中, a1a2ar的直接后继是的直接后继是 a1a2ak-1 (ak+1)(ak+r-k+1).例例 1： 应用算法生成应用算法生成1,2,6的的 4-组合组合.定理定理 4.4.2 1,2,n的的 r-组合组合 a1a2ar出现在出现在1,2,n的的 r-组合中的字典序中的位置号如下组合中的字典序中的位置号如下:- rn ra-n1 1-ra-n2 2a-n1-r 1a-nr例例 2： 求求1,2,8的的 4-组合中组合中 1258 的字典序位置的字典序位置.4.5 偏序和等价关系偏序和等价关系定义定义 1： 设设 X 是一个集合，是一个集合，X 上的关系定义为上的关系定义为 X X 上的子集（其中上的子集（其中 X X 是集合是集合 X 的序偶的的序偶的 集合，即集合，即 X X=（a,b） a,bX ） ，令关系，令关系 R X X，若（，若（a,b）RR , ,则称则称 a a 和和 b b 有关有关系系 R R，记为，记为 aRb;aRb;否则称否则称 a a 和和 b b 没有关系没有关系 R R , ,记为记为 ab.R定义定义 2： 设设 R 是是 X 上的关系，上的关系，R=(x,y)| | x, yX 且且 xRy , 那么那么 R 可能具有下列性质可能具有下列性质: (1)自反性自反性: 若对若对 xX, 均有均有 xRx;(2)反自反性反自反性: 若对若对 xX, 均有均有 xx;R(3)对称性对称性: 对对 x,yX, 若若 xRy, 则必有则必有 yRx;(4)反对称性反对称性: 对对 x,yX, x y, 若若 xRy; 则必有则必有 yx;R(5)传递性传递性: 对对 x,y,zX, 若若 xRy, yRz, 则必有则必有 xRz;定义定义 3: 设设 R 是是 X 上的二元关系上的二元关系 (1)偏序关系偏序关系:若若 R 满足自反性满足自反性, 反对称性和传递性反对称性和传递性, 则称则称 R 是是 X 上的偏序关系上的偏序关系. 记记 为为” ”. 在其上定义了偏序关系的集合称偏序集在其上定义了偏序关系的集合称偏序集, 记为记为(X,