组合数学（张永刚）吉林大学 第三章 基本计数方法及应用.pptVIP

例3.2.7 10个人围坐圆桌旁聚餐，如果A和B不能相邻，则不同的坐法有多少种 解不考虑限制条件，10个人的圆排列数为9！，考虑A和B相邻的情况，有两种情形A在B的左侧和A在B的右侧，则A和B相邻的圆排列数为2×8！， 9！-2×8！=7×8！=282240种 例3.2.8 将5个不同颜色的珠子串成一条项链，能够串成多少不同的项链。 解 4！=24个不同5-圆排列。但这个问题很特殊，因为项链可以翻转但不影响珠子的相对位置，即每2个圆排列对应同一个项链，所以有 12个不同的项链。 §3.2.2 集合排列和组合的生成 （1）排列的生成 （a）邻位互换法 源自递归思想 1 2 1 2 3 1 3 2 3 1 2 邻位互换法： 活动状态 箭头所指的相邻数比该数小。 算法3.1 邻位互换法生成1,2 ,…,n的所有排列 输入：n 输出：{1,2,…,n}的所有n!个全排列 步骤1：初始化，设 ，输出P； 步骤2：考虑排列P，若排列中无一处于活动状态，则停止； 步骤3：求所有处于活动状态的数中的最大者，设为pm。pm和它的箭头所指的一侧的相邻数互换位置，输出P； 步骤4：令比pm 大的所有数的箭头改变方向，转步骤2. 当n=4时，算法生成各个排列的顺序 （b）字典序法 例：?字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。注意 一个全排列可看做一个字符串，字符串可有前缀、后缀。　　 生成给定全排列的下一个排列 所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。 2314 2341 (a) 求满足Pj-1＜Pj的j的最大值，设为i,，即 i=max｛j| Pj-1＜Pj} 求满足Pi-1＜Pk的k的最大值，设为j，即 j=max｛k| Pi-1＜Pk} Pi-1与Pj互换，得 中 P1P2P3P4…Pj-1Pj… i 部分的顺序逆转，得到的 便是所求的下一个排列。 例： P1P2P3P4=3421 (a) i=max｛j| Pj-1＜Pj}=2 (b) j=max｛k| Pi-1＜Pk}=2 (c) P1与P2互换得4321 (d) 4321中的321的顺序逆转得排列： 4123 P1P2P3P4=2431 (a) i=max｛j| Pj-1＜Pj}=2 (b) j=max｛k| Pi-1＜Pk}=3 (c) P1与P2互换得3421 (d) 3421中的421的顺序逆转得排列： 3124 序号 排列 序号 排列 1 1234 13 3124 2 1243 14 3142 3 1324 15 3214 4 1342 16 3241 5 1423 17 3412 6 1432 18 3421 7 2134 19 4123 8 2143 20 4132 9 2314 21 4213 10 2341 22 4231 11 2413 23 4312 12 2431 24 4321 （2）组合的生成 （a）生成集合I={1,2,…,n}的所有组合 算法3.3 按字典序生成所有长度为n的二进制数串 输入：n 输出：所有长度为n的二进制数串 步骤1：初始化，设 ，输出P; 步骤2：如果对于所有的i，若pi=1，则算法终止； 步骤3：求满足pj=0的j的最大值i，即i=max{j| pj=0}； 步骤4：令pi=1，且pi+1=0，pi+2=0，…，pn=0，得到新的数串P，输出P并转步骤2. 1 2 3 空集 0 0 0 ｛3｝ 0 0 1 0 1 0 ｛2，3｝ 0 1