生成排列和组合

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第四章 生成排列和组合,4.1,生成排列,上一章我们讨论了排列和组合的有关计数问题，本章我们将讨论排列和组合的某些排序方案以及执行这些方案的算法，如何编码,;,还要讨论两个重要的案例：偏序关系和等价关系。,由前面知识可知，,n,个正整数组成的集合：,1,2,3,.,n,有,n,!,个,排列，只要,n,稍大，,n,!,的值,1,也很大，例如,15!,比,1 000,000,000,000,还大。,Stirling,公式给出一个有用并且方便的计,算方法：,n,!,随着,n,，,他们的值就越接近。在许多高等数学书中都有证明，我们本小节的目的，是要构造一个简单生成集合,1,2,3,n,的所有排列的算法。观察发现：,如果整数,n,从,1,2,3,n,的一个排列中删除，那么结果则是,1,2,3,n,-1,的一个排列。,2,例如：我们从,1,2,3,5,的,排列中任意找一个,3,4,5,1,2;,删去,5,后得到,3,4,1,2;,这个四个数的排列刚好也可以从,1,2,3,4,的,排列中得到。它们的关系如右：,反之,求,1,2,3,.,n,的排列,也可以先求,1,2.,n,-1,的排列,再把,n,插在,各个元素之间而得到,1,2,3,.,n,的排列。,5,3,4,1,2,3,5,4,1,2,3,4,5,1,2,3,4,1,5,2,3,4,1,2,5,3,这里介绍全排列两种算法：,(,A),字典序法,(,B),错位置排法,(,A),字典序法,对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个,全排列,的先后是从左到右逐个比较对应的字符的先后，数字按由小到大、字母按英文字母表顺序。,4,例 字符集,1,2,3,按较小的数字较先,生成的全排列按字典序的顺序是,:,(123),(132),(213),(231),(312),(321),这六个三位数数是按由小到大的顺序排列的。,一个全排列可看做一个字符串，字符串可以有,前缀,、,后缀,。例如,1,2 3,和,1,3 2,生成给定全排列的下一个排列,所谓,一个的下一个,就是这一个与下一个,5,之间,没有其他的,。这就要求这一个与下一个,有尽可能,长,的,共同前缀,，也即变化限制在尽可能,短,的,后缀,上。,例,839647521,是,1-9,的排列。1,-,9的排列最前面的是123456789，也,是,1-9,的排列中数值最小的；最后面的是987654321，也,是,1-9,的排列中数值最大的；,从右向左扫描若都是增,的，就到,了,987654321，也就没有下一个了。,6,我们对一个给定的排列寻找按字典序紧接的,下一个排列，就是要尽可能保留长的共同,前缀,，而去修改不同的字符和,后缀,。我们给出这样一种方法：,1.,对给定的排列，从右到左扫描各个字符，如,果这些字符从右到左是按字典序递,增,的,，该,排列就是最后一个，没有下一个排列。,7,2.,从右到左扫描各个字符，如果第,k,个字符不是按字典序递,增,的,，下一个排列可以将第,k,个字符增加一位后修改得到。,3.,将第,k,个字符增加一位后，可能与该字符前缀中的字符重复，那就再增加一位，直到与前缀中的字符不重。,4.,若第,k,个字符增加一位后，仅与该字符后缀中的字符重复，那就与后缀中重复的字符互换。,8,5.,执行第,4,步后，保留前缀和新的第,k,个字符，将后缀的字符按字典序重新排列就得到原排列紧接的排列。,例 按字典序求,8396,4,7521,的下一个排列，,解：最大的,9-,排列在最后，对于该排列，从右向左找出比右边数字,小,的第一个数,4,，将它加,1(,加后不与前缀的数字重复,),变成,5,；,9,再对后缀从小到大重新排序,1257,，修改后缀中的重复数字,5,为,4,，接上前缀,8396,得到,8396,5,12,4,7,，即是原排列,839647521,的下一个排列,.,例 按字典序求集合,a,b,c,d,e,的一个,5-,排列,ebadc,下一个排列,.,解：英文字母序是：,abcde,；将,5-,排列,eb,a,dc,从右向左扫描，从右向左找出比右边字母,先,的第一,10,个字母,a,，将它增加,1,位变成,b,后与前缀中的字母重复，再将它增加,1,位变成,c,后不与前缀中的字母重复，保留前缀,eb,将,a,换成,c,，把后缀,dc,中的重复字母,c,换成,a,，对新后缀按字典序重新排列成,ad,；即得到新的排列是,:,ebcad,；,这个排列就是紧接着,5-,排列,ebadc,最近的一个排列。,11,(,B),错位排法,当,n,=1,，,排列方式只有一种，就是,1,。,当,n,=2,时，先将惟一的,1-,排列,1,写出两次，并错位置插入,2,，即得两个,2-,排列如下：,1,2,2,1,当,n,=3,时，先将两块,2-,排列分别写出,3,次，,12,并错位置插入,3,，即得,3!=6,个,3,排列如下：,1 2,3,1,3,2,3,1 2,3,2 1,2,3,1,2 1,3,当,n,=4,时,先将,6,块,3-,排列分别写出,4,次,并错位置以,4,即得,4!=24,个,4,排列。,13,1 2 3,4,1 2,4,3,1,4,2 3,4,1,2 3,4,1 3 2,1,4,3 2,1 3,4,2,1 3 2,4,3 1 2,4,3 1,4,2,3,4,1 2,4,3 1 2,4,3 2 1,3,4,2 1,3 2,4,1,3 2 1,4,2 3 1,4,2 3,4,1,2,4,3 1,4,2 3 1,4,2 1 3,2,4,1 3,2 1,4,3,2 1 3,4,14,考察,4,排列的生成过程，不难发现，按,4,的走向可,将全部排列分成,(4-1),！,=6,块,其中每一块的其余排列均可用前一排列交换,4,与相邻数字而得。对于,1,2,n,，,最后一个排列交换最后两个数字而得。进而考察,n,(,n,4),排列的生成过程可知，相邻块交界处两个排列的数字交换并不一定发生在,边界处，而是按照,n,-1,排列的生成顺序交换相邻数字。,15,求,n,排列时，不用保存,(,n,-1)!,个,n,-1,排列，而,只需要利用一个,n,位长的一维数组存放一个,n,排列，然后每次对它交换某相邻数据产生下一个,n,排列。求算过程中，每产生一个,n,排列，即行输出，输出不能集中到最后。因为只给出了一个排列的存储空间，后边的结果会代替前边的结果。,16,给定一个整数,k,，,我们用 或 表示,k,具有向,右或向左的方向。,在,1,2,n,的一个排列中，若每个整数均具有指定的方向，且,若某个整数,k,的方向所指的,k,的相邻元素比,k,小,，则称,k,在该排列中是,活动的,。例如，对于排列：,其中,6,3,5,是活动的,因为,6,3,5,右边的数比自己小。,17,一个排列中所有活动整数的最大者称为该排列,的,最大活动整数,。例如，上述例子中,6,是最大活动整数。由此可知，,1,2,3,.,n,的排列中，,1,是不可能活动的，除下列两种情况外，,n,总是活动的。,1),n,是第一个整数而且它的箭头指向左：,2),n,是最后一个整数而且它的箭头指向右：,下面我们给出,生成所有排列的算法,：,18,0.,输正整数,n,；,1.,构造第一个排列,1,2,n,，,并初始化各数的,方向为 ；,2.,当当前排列中存在活动整数时，做,:,）找出当前排列的最大活动整数,m,(,可能随它的位置而发生改变,),；,）,交换,m,和其它所指向的相邻整数；,）改变所有满足,p,m,的整数,p,的方向；,）以上处理的结果生成了一个新的排列,19,我们就,n,=4,叙述该算法。结果用三列显示：,由于在 中除,4,外没有活动整数，算法终止,。,20,对错位置数生成,n,！,个全排列的改进算法,1,对某个选中的,n,-1,排列，置,n,于最右端得到一个,n,排列；,2,令,n,由右向左与相邻数字交换，每交换一次即得一个,n,排列,(,共可得,n,-1,个,n,排列,),；,3,当,n,到达最左端时，若,n,!,个,n,排列均已生成，转,7,；否则，令除,n,以外的数,n,-1,按,2,交换最大数字相邻的数字，得到下一个,n,-1,排列，连同最左端的,n,构成一个,n,排列；,21,4,令,n,由反向由左向右与相邻数字交换，每交,换一次即得一个,n,排列,(,共可得,n,-1,个排列,),；,5,当,n,到达最右端时，若,n,!,个,n,排列均已生成，转,7,；否则，令,除,n,以外的数,n,-1,按,2,交换最大数字相邻的数字,得到下一个,n-,1,排列，连同最右端的,n,构成一个,n,排列；,6,返回,2,；,7,结束。,22,这里有一个求,r,-,排列的程序，提供给大家参考,：,此算法以字典序升序列出,1,2,.,n,的所有排列,输入：,n,输出：以字典序升序列出,1,2,n,的所有排列。,1.,procedure,permutation(n),2.,for,i:=1,to,n,do,3.,S,i,:=i,4.,print,s,1,s,n,/,打印第一个排列,23,5.,for,i:=2,to,n!,do,6.,begin,7.m:=n-1,8.,while,s,m,s,m+1,do,9./,从右边找到第一个减少,10.m:=m-1,11.k:=n,12.,while,s,m,s,k,do,13./,找到,s,m,s,k,的最右元素,14.k:=k-1,24,15.,swap(s,m,s,k,),16.p:=m+1,17.q:=n,18.,while,pq,do,19./,交换,s,m+1,和,s,n,交换,s,m+2,和,s,n-1,等。,20.begin,21.swap(s,p,s,q,),22.p:=p+1,23.q:=q-1,25,24.,end,25.,print,s,1,s,n,/,打印第,i,个排列,26.,end,27.,end,permutation,大家可以上机运行上述程序。,26,4.2,排列中的逆序,假设,i,1,i,2,i,n,是集合,1,2,n,的一个排列。如果存在,k,i,l,则称数对,(,i,k,i,l,),为,该排列中的一个,逆序,(,反序,),，,即前面的元素大于后面的元素，不一定是排列中相邻的元素，例如：,排列,31524,中有四个逆序，分别是：,(3,1),(3,2),(5,2),(5,4),。,集合,1,2,n,的排列中唯一没有逆序的排列是：,1,2,n,。,27,对于排列,i,1,i,2,i,n,我们定义非负整数,a,j,(,j,1,2,n,),是该排列中逆序数的总和。其中整数,j,是重要的第二成分，并称,a,j,为整数,j,在该排列中的,逆序数,。,a,j,表示了排列中的逆序数量，但它是相对整数,j,来,计算的，换句话说：,a,j,等于在排列中先于,j,但,大于,j,的,整数的个数，即,j,之前比,j,大的数的数量；它度量了,j,反序的,程度。,28,对于逆序数,a,j,而言，自身又能够成一个数字序,列：,a,1,a,2,a,n,;,我们把这个数字序列叫做原排列,i,1,i,2,i,n,的,逆序列,。,数,a,1,a,2,+,a,n,可以度量原排列的无序程度，它的值越大，说明相应的排列的,无序程度,越大。,例：在集合,1,2,3,4,5,中有排列,31524,，,12345,，,54321,。下表给出了每个排列的逆序和相应的逆序列：,29,排 列,逆 序,逆 序 列,a,1,a,2,a,3,a,4,a,5,3 1 5 2 4,(3,1),(3,2),(5,2),(5,4),1,2,0,1,0,1 2 3 4 5,无,5 4 3 2 1,(5,4),(5,3),(5,2),(5,1),(4,3),(4,2),(4,1),(3,2),(3,1),(2,1),4,3,2,1,0,30,对于排列,3 1 5 2 4,