Chap1-2排列组合生成、可重组合.ppt

1.6全排列的生成算法 全排列的生成算法就是对于给定的字符集 ，用有效的方法将所有可能的全排列无重复 无遗漏地枚举出来。 这里介绍4种全排列算法： (A) 直接生成法 (B) 序数法 (C) 字典序法 (D) 换位法 1.6.1 直接生成法 递推算法：假设已经生成n-1个数的所有(n-1)! 个全排列，将n插入到每一个排列的前面、第 12之间、第23之间、。最后，即得到n个 数的所有n(n-1)!=n! 个全排列。 优点是生成简便，缺点是速度慢。 1.6.2 序数法 n的十进制表 示: n的p进制表示 1. 6.2 序数法 我们来看另一种表示 n!=(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)!+22!+2! 不难证明，从0到n!-1的任何数m可唯一的表示为 其中 所以从0到n!-1的n!个整数与 (an-1,an-2,a2,a1) 一一对应。 另一方面，不难从m算出an-1,an-2,a2,a1. 1. 6.2 序数法 算法如下： . 1. 6.2 序数法 1. 6.2 序数法 反过来, 由(a3,a2,a1)= (301)也可以得到排列4213 ， 下面我们试图将n-1个元素的序列(an-1,a1)与n 个元素的排列建立起一一对应关系. 其中 例 p=4213 (a3,a2,a1)= (301) _ _ _ _ 432 1 而a2=0,说明3的右边没有比它更小的，故3放在最 右端， 考虑a1=1,容易得出，2右边还有一个空格放1，于 是得到了排列4213。 由a3=3, 知4放在空格的最左端, 1. 6.2 序数法 方法如下 1. 6.2 序数法 这个算法的优点是建立了自然序数和排列之 间的一一对应关系（通过n-1个元素的序列 (an-1,a1) ）。 缺点是这种对应关系需要通过序列转换， 即两层对应关系，多一层计算量。 1.6.3字典序法 字典序：对于两个序列a1ak和b1bk ，若存在t，使 得ai=bi, i2 2 41 1 在后缀7521中找出比4大的数7 5找出其中比4大的最小数 5 5 4 、5 对换 8396 7 215 4 后缀变为7421 将此后缀翻转 12 4 7 接上前缀83965得到839651247 即839647521的下一个。 例 为后缀 大于4的用橙色表示 小于4的用绿色表示 找出比右边数字小的第一个数4 1.6.3字典序法 一般而言，设P是1,n的一个全排列。 P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1Pn P= P1P2Pj-1PkPnPk+1PjPk-1Pj+1即是P的下一个 对换Pj，Pk，将Pj+1Pk-1PjPk+1Pn翻转， j=maxi|PiPj 该算法的优点是排列清晰，而且保持着字典序。 缺点是算法较繁琐。 1.6.4换位法 给定n-1的一个排列,将n 由最右端依次插入排 列 ，即得到n个n的排列： p1 p2npn-1 np1 p2pn-1 p1 p2pn-1n 基于直接生成法 n的全排列可由n-1的全排列生成： (1) 1 (2) 1 1 例, n=4 (3) 1 2 1 2 2 1 2 1 1 2 2 1 3 3 3 3 3 3 2 2 1 2 3 1 2 3 1 2 3 1 2 3 1 3 2 1 3 2 1 3 2 1 3 2 3 1 2 3 1 2 3 1 2 3 1 2 3 2 1 3 2 1 3 2 1 3 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 3 2 1 3 2 1 3 2 1 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 对上述过程，一般地，对i，将前一步所得的每 一排列重复i次，然后将i由第一排的最后往前移 ，至最前列，正好走了i次,下一个接着将i放在 下一排列的最前面，然后依次往后移，一直下 去即得i元排列。 对给定的一个整数k，我们赋其一个方向，即在 其上写一个箭头（指向左侧或右侧） 下面我们用较正式的语言来说这件事。 kk或者 1.6.4换位法 考虑1,2n的一个排列，其上每一个整数都给 了一个方向，我们称整数k是可移的 (Mobile 2)若r = n, 则 N= 3)若r n, 则 N=0; 2)若r = n, 则 N=1; 3)若r n ,且对所有的i, ,则N=C(k+r- 1,r); 4)若r n ,且存在i, , 则对N没有一般 的求解公式，具体解法以后再说。 1.8.2可重组合 取r个无区别的球放进k个有标志的盒子，每个 盒 子中的球的数目不加限制, 允许重复的组合数 即 其方案数。 典型模型 定理1.3 线性方程 的非负整数解的个数为C(k+r-1,r) 。 1.8.3不相邻的组合 不相邻的组合是指从n=1,2,n中取r 个，不允许重复且不存在i,i+1两个相邻的 数同时出现于一个组合中的组合. 定理1.4 从n=1,2,n中取r个作不相 邻的组合，其个数为C(n-r+1,r). 1.8.3 不相邻