排列组合生成算法课件

1.6全排列的生成算法这里介绍3种全排列算法：(A)序数法(B)字典序法(C)换位法1.6.1序数法n的十进制表示：n的p进制表示我们来看另一种表示 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)!+2*2!+2!不难证明，从0到n!-1的任何数m可唯一的表示为 m=an-1(n-1)!+an-2(n-2)!+a11!,其中0 ai i.所以从0到n!-1的n!个整数与 (an-1,an-2,a2,a1)一一对应。另一方面，不难从m算出an-1,an-2,a2,a1.=算法如下：m=m1,0 m n!-1 m1=2m2+k1,0 k1 1 m2=3m3+k2,0 k2 2 .mn-2=(n-1)mn-1+kn-2,0 kn-2 n-2 mn-1=kn-1,0 kn-1 n-1 (kn-1 k2k1)m下面我们试图将n-1个元素的序列(an-1,a1)与n个元素的排列建立起一一对应关系设序列(an-1,a1)对应某一排列p=p1p2pn,其中 ai：排列p中数i+1所在位置的右边比i+1小的数的个数,i=1,2,n-1例 p=4213-(a3,a2,a1)=(301)反过来，由(a3,a2,a1)=(301)也可以得到排列4213，方法如下由a3=3,4放在空格的最左端,_ _ _ _432 1而a2=0,说明3的右边没有比它更小的，故3放在最右端，考虑a1=1,容易得出，2右边还有一个空格，放1，于是得到了排列4213。实际上，我们可以从1开始构造排列1，写下 12，考虑a1,它只可取0或1，若取0，则2必在1的后边，否则，它在1的前边。3，考虑a2,它可取0,1,2.若取0，3必放在上一步得到的两个数的排列的后边，若a2=1,则3必放在第二步得到的两数的排列的中间，若a2=2,则3必放在第二步得到的排列的两数的前边，1k+1，考虑ak,0 ak k,(1),ak=0,k+1必放在第k步得到的排列的这k个数的最后面；(2),ak=1,k+1必放在第k步得到的排列的这k个数的倒数两个数中间，.(j),ak=j,k+1必放在第k步得到的排列的这k个数的倒数j,j+1这两个数之间；.1.6.2字典序法 对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。1.6.2字典序法 例例 字符集1,2,3,较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。一个全排列可看做一个字符串，字符串可有前缀前缀、后缀后缀。1.6.2字典序法1）生成给定全排列的下一个排列所谓一个的下一个一个的下一个就是这一个这一个与下一个下一个之间没有其他的没有其他的。这就要求这一个与下一个有尽可能长长的共同前缀共同前缀，也即变化限制在尽可能短短的后缀后缀上。1.6.2字典序法 例例 839647521是1-9的排列。19的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。1.6.2字典序法求83964 47521的下一个排列7 5 2 1 747 42 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的用绿色表示 找出比右边数字小的第一个数41.6.2字典序法一般而言，设P是1,n的一个全排列。P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1Pnj=maxi|PiPj对换Pj，Pk，将Pj+1Pk-1PjPk+1Pn翻转，P=P1P2Pj-1PkPnPk+1PjPk-1Pj+1即P的下一个1.6.3换位法思想n的全排列可由n-1的全排列生成：给定n-1的一个排列,将n 由最右端依次插入排列，即得到n个n的排列：p1 p2npn-1np1 p2pn-1p1 p2pn-1n (1)1(2)1(3)1例,n=4(3)1 21 22 12 11 22 133333322(4)1 2 3(5)1 2 3(6)1 2 3(7)1 2 3(8)1 3 2(9)1 3 2(10)1 3 2(11)1 3 2(12)3 1 2(13)3 1 2(14)3 1 2(15)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 3444444444444444444444444对上述过程，一般地，对i，将前一步所得的每一排列重复i次，然后将i由第一排的最后往前移，至最前列，正好走了i次,下一个接着将i放在下一排列的最前面，然后依次往后移，一直下去即得i元排列。下面我们用较正式的语言来说这件事。对给定的一个整数k，我们赋其一个方向，即在其上写一个箭头（指向左侧或右侧）或者kk考虑1,2n的一个排列，其上每一个整数都给了一个方向，我们称整数k是可移的(Mobile&Active),如果它的箭头所指的方向的邻点小于它本身。例如中6、3、5都是可移的。显然1永远不可移，n除了以下两种情形外，它都是可移的:(1)n是第一个数，且其方向指向左侧(2)n是最后一个数，且其方向指向右侧于是，我们可由按如下算法产生所有排列算法1，开始时：2，当存在可移数时(a)找最大的可移数m(b)将m与其箭头所指的邻数互换位置(c)将所得排列中比m大的数p的方向调整，即改为相反方向。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 34444444444444444444444441.7组合的生成设从1,n中取r元的组合全体为C(n,r).C1C2CrC(n,r).不妨设C1C2Cr iCi(nr+i),i=1,2,r 令j=maxi|Cinr+i.则C1C2Cr的下一个组合为C1C2Cj-1(Cj+1)(Cj+2)(Cj+rj+1)这等于给C(n,r)的元素建立了字典序字典序。12r的序号为0，n-r+1 n-r+2n的序号为C(n,r)11.7组合的生成例 在C(10,4)中 4679的序号是首位小于4的组合的个数；首位是4，第2位小于6的组合的个数；前2位是46，第3位小于7的组合的个数；前3位是467，第4位小于9的组合的个数之和。反之，也可以由序号求组合。1.8 多重集的排列和组合多重集多重集元素可以多次出现的集合，即元素可以重复。我们把某个元素ai出现的次数ni(ni=0,1,2,)叫做该元素的重复数，通常把含有k种不同元素的多重集S记作1.8.1可重排列定义 从一个多重集中有序选取的r个元素叫做S的一个r-(可重)排列。当时也叫做S的一个排列.定理定理 设多重集则的r-(可重)排列数是rk推论推论 例例 求不多于4位数的二进制数的个数解：所求的标志数是多重集2红旗，3黄旗的排列数，故N=5!/(2!*3!)=10例例 用两面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志？总结总结设则S的r-排列数N满足：1)若r n,则N=0;2)若r=n,则 N=3)若r n,且对所有的i,则4若r n,则N=0;2)若r=n,则 N=13)若r n,且对所有的i,则N=C(k+r-1,r)4若r n,且存在i,则对N没有一般的求解公式，具体解法以后再说。1.8.2可重组合典型模型取r个无区别的球放进n个有标志的盒子，每个盒子中的球的数目不加限制，允许重复的组合数即其方案数。定理定理1.3 r个无区别的球放进n个有标志的盒子，每个盒子中的球的数目不限的方案数是C(n+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不相邻的组合证明证明：用两种方法计算n的无重不相邻组合C(n,r)的计数问题解法1 00100100100100 其中不可含11 /共n位r个1 /以1结尾：r-1个10与n-1-2(r-1)个0的排列r-1+n-1-2(r-1)=n-r这样的排列有 (n-r)!=(r-1)!(n-2r+1)!()n-rr-11.8.3不相邻的组合以0结尾：r个10与n-2r个0的排列 r+n-2r=n-r 这样的排列有()个 ()+()=()n-r r n-r n-r n-r+1r-1 r r1.8.3不相邻的组合解法任给a1a2arC(n,r),a1 a2 ar令f：a1a2arb1b2brbi=ai-i+1,i=1,2,r.1b1 b2 br n-r+1,b1b2brC(n-r+1,r)C(n,r)=C(n-r+1,r)谢谢