排列组合生成算法

1.6全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。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!-1m1=2m2+k1,0≤k1≤1m2=3m3+k2,0≤k2≤2…………….mn-2=(n-1)mn-1+kn-2,0≤kn-2≤n-2mn-1=kn-1,0≤kn-1≤n-1(kn-1…k2k1)←→m下面我们试图将n-1个元素的序列(an-1,…,a1)与n个元素的排列建立起一一对应关系设序列(an-1,…,a1)对应某一排列p=p1p2…pn,其中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放在空格的最左端,____4321而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的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。1.6.2字典序法求839647521的下一个排列752174＜74<554>224>11在后缀7521中找出比4大的数75找出其中比4大的最小数554、5对换839672154后缀变为7421将此后缀翻转1247接上前缀83965得到839651247即839647521的下一个。[例]为后缀大于4的用橙色表示小于4的用绿色表示找出比右边数字小的第一个数41.6.2字典序法一般而言，设P是[1,n]的一个全排列。P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pnj=max{i|Pi<Pi+1},k=max{i|Pi>Pj}对换Pj，Pk，将Pj+1…Pk-1PjPk+1…Pn翻转，P’=P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个1.6.3换位法 思想[n]的全排列可由[n-1]的全排列生成：给定[n-1]的一个排列п,将n由最右端依次插入排列п，即得到n个[n]的排列：p1p2…npn-1np1p2…pn-1…p1p2…pn-1n(1)111例,n=4(3)33333322123123123123132132132132312312312312321321321321231231231231213213213213444444444444444444444444对上述过程，一般地，对i，将前一步所得的每一排列重复i次，然后将i由第一排的最后往前移，至最前列，正好走了i次,下一个接着将i放在下一排列的最前面，然后依次往后移，一直下去即得i元排列。下面我们用较正式的语言来说这件事。对给定的一个整数k，我们赋其一个方向，即在其上写一个箭头（指向左侧或右侧）或者考虑{1,2…n}的一个排列，其上每一个整数都给了一个方向，我们称整数k是可移的(Mobile&Active),如果它的箭头所指的方向的邻点小于它本身。例如中6、3、5都是可移的。显然1永远不可移，n除了以下两种情形外，它都是可移的:(1)n是第一个数，且其方向指向左侧(2)n是最后一个数，且其方向指向右侧于是，我们可由按如下算法产生所有排列算法1，开始时：2，当存在可移数时找最大的可移数m将m与其箭头所指的邻数互换位置将所得排列中比m大的数p的方向调整，即改为相反方向。1231231231231321321321323123123123123213213213212312312312312132132132134444444444444444444444441.7组合的生成 设从[1,n]中取r元的组合全体为C(n,r).C1C2…Cr∈C(n,r).不妨设C1＜C2＜…＜Cri≤Ci≤(n－r+i),i=1,2,…,r令j=max{i|Ci＜n－r+i}.则C1C2…Cr的下一个组合为　　　C1C2…Cj-1(Cj+1)(Cj+2)…(Cj+r－j+1)这等于给C(n,r)的元素建立了字典序。12…r的序号为0，n-r+1n-r+2…n的序号为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-(可重)排列数是推论例求不多于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,且存在i,,则对N没有一般的求解公式，具体解法以后再说。1.8.1可重组合允许重复(可重)的组合是指从中取r个元素,允许重复，即允许的数同时出现于一个组合中的组合,其全体记为C(k,r),其个数记为C(k,r)定理1.2从中取r个作可重的组合，其个数为C(k+r-1,r)1.8.2可重组合 C(n,r)的计数问相当于r相同的球放入n个互异的盒子，每盒球的数目不同的的计数。而后一问题又可转换为r个相同的球与n-1个相同的盒壁的排列的问题。 易知所求计数为=C(n+r-1,r) 即　C(n,r)=()=C(n-1,r)+C(n,r-1) 不含“１”至少含一个“１”(n-1+r)!————r!(n-1)!n+r-1rr个相同的球/\———————　————————／　　　　　　　　　　　　　　　\0…010…01…10…0\/————————　　　　　\/　n-1个相同的盒壁1.8.2可重组合 另证　设a1a2…ar∈C(n,r)　　　　　1≤a1≤a2≤…≤ar≤n, 令C(n,r)上的f，使得bi=ai+i-1,i=1,2,…,r. 则b1b2…br满足1≤b1＜b2＜…＜br≤n+r-1b1b2…br∈C(n+r-1,r) f：a1a2…ar→b1b2…br 显然f是单射，f：b1b2…br→a1a2…ar－－-11.8.2可重组合 ai=bi-i+1,i=1,2,…,r. a1a2…ar∈C(n,r) f是单射　　C(n,r)≤C(n+r-1,r) f是单射　C(n,r)≥C(n+r-1,r) ∴C(n,r)=C(n+r-1,r) 第二个证明可说一种“拉伸压缩”技巧。不可谓不巧妙。但仍不如第一证明来的明快，由此可见组合证明的功效。———-1—推论1推论2任取一个所求的r-组合，从中拿走每个元素一个就得到S的一个r-k-组合，反之,对于S的一个r-k-组合，加入元素a1,a2,…ak就得到所求组合，所以其组合数即为S的r-k-可重组合数。总结设则S的r-组合数N满足：1)若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.3r个无区别的球放进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)的计数问题 解法10…010…010…010…010…0 其中不可含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-rrn-rn-rn-r+1r-1rr1.8.3不相邻的组合解法２　　任给a1a2…ar∈C’(n,r),　a1＜a2＜…＜ar令f：a1a2…ar→b1b2…brbi=ai-i+1,i=1,2,…,r.1≤b1＜b2＜…＜br≤n-r+1,　　　　　b1b2…br∈C(n-r+1,r)C’(n,r)=C(n-r+1,r)