1、1 组合数学组合数学 第二讲第二讲排列组合生成算法排列组合生成算法2第二讲第二讲 : 排列组合的生成算法排列组合的生成算法(1) 存在存在 : 满足一定条件配置的存在性满足一定条件配置的存在性 . (2) 计数：计数： 计算出满足条件配置的数目计算出满足条件配置的数目 .(3) 算法：算法： 构造所有配置的算法构造所有配置的算法 .(4) 优化：优化： 优化算法优化算法 .组合数学的主要问题组合数学的主要问题 :3一一 . 排列生成算法排列生成算法l 排列生成有几种典型算法排列生成有几种典型算法 , 这些算法这些算法都很有成效都很有成效 . 它们在实际中具有广泛它们在实际中具有广泛应用价值应用
2、价值 . 1. 序数法序数法2. 字典序法字典序法3. 邻位互换法邻位互换法 (Johnson-Trotter)4. 轮转法轮转法 41. 序数法序数法 l序数法基于一一对应概念序数法基于一一对应概念 . l先在先在 排列排列 和一种特殊的和一种特殊的 序列序列 之间建立之间建立 一一种一一对应关系种一一对应关系 , 然后再给出由序列产然后再给出由序列产生排列的方法生排列的方法l因为序列的产生非常方便因为序列的产生非常方便 , 这样我们就这样我们就可以得到一种可以得到一种 利用序列来生成排列的方利用序列来生成排列的方法法 .l如何建立这种一一对应如何建立这种一一对应 ? 5l思路类似数的思路类
3、似数的 10进制、进制、 2进制和进制和 p进制进制表示表示 .6l这相当于自然数与某种序列之间建立这相当于自然数与某种序列之间建立了一一对应关系了一一对应关系 . l可以利用置换来表示整数可以利用置换来表示整数 :n!=n(n-1)! =(n-1+1)(n-1)!= (n-1) (n-1)!+(n-1)!(n-1)!= (n-2) (n-2)!+(n-2)!n!= (n-1) (n-1)!+ (n-2) (n-2)!+ (n-3) (n-3)!+ +22!+11!+17ln!-1=(n-1) (n-1)! +(n-2) (n-2)!+(n-3) (n-3)!+ +2 2!+11!l可以证明可
4、以证明 , 从从 0到到 n!-1之间的任何整数之间的任何整数 m都可唯一地表示为都可唯一地表示为 :m=an-1 (n-1)!+an-2 (n-2)!+ +a2 2!+a1 1! 其中其中 0aii, i=1,2, ,n-1.lm与序列与序列 (an-1,an-2 , a2,a1)一一对应一一对应l书中有确定这些系数的方法书中有确定这些系数的方法 .l 例如：例如： 10 13! 22! 01!8l因为满足条件因为满足条件0aii, 1in-1 （ 2.1）的序列的序列(an-1, an-2, , a2, a1)共有共有 n!个个 , 这恰好与这恰好与 0到到 n!-1的的 n!个整数一个整
5、数一一对应一对应 . l需要建立满足条件需要建立满足条件 (2.1)的的 n!个序列个序列(an-1, an-2, , a2, a1)和和 n元集合元集合 S的的全部排列之间的一一对应关系全部排列之间的一一对应关系 .9l还需要给出一种办法还需要给出一种办法 , 由每个满足条件由每个满足条件(2.1)的序列的序列 (an-1,an-2, ,a2,a1)可生成唯可生成唯一的一个排列一的一个排列 .l这样我们就可以产生出所有的排列这样我们就可以产生出所有的排列 . l怎么样由一个满足条件怎么样由一个满足条件 (2.1)的序列产的序列产生一个生一个 n阶排列阶排列 ?l如何把如何把 1,2, n的一
6、个排列与一个满足的一个排列与一个满足条件条件 (2.1)的序列建立起直接的关系的序列建立起直接的关系 ?10l行列式定义中有行列式定义中有 逆序数逆序数 的概念的概念 , 就是一就是一个排列中违反自然顺序的数对个排列中违反自然顺序的数对 : 比如比如12354的逆序数为的逆序数为 1, 而而 43215的逆序数的逆序数为为 6. l设设 p1p2 pn是任意一个是任意一个 n元排列元排列 , 则则 i+1后面比后面比 i+1小的数字的个数小的数字的个数 ai总不超过总不超过 i, 即即 aii, i=1,2, n-1.l这样自然由一个排列得到一个序列这样自然由一个排列得到一个序列(an-1,an-2, ,a2,a1), 而且满足条件而且满足条件 (2.1).
