生成排列和组合.ppt

第四章第四章 生成排列和组合生成排列和组合 4.1 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,23,5,4,1,23,4,5,1,23,4,1,5,23,4,1,2,53这里介绍全排列两种算法：这里介绍全排列两种算法：(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.对给定的排列，从右到左扫描各个字符，如对给定的排列，从右到左扫描各个字符，如 果这些字符从右到左是按字典序递果这些字符从右到左是按字典序递增增的的，该，该 排列就是最后一个，没有下一个排列。排列就是最后一个，没有下一个排列。72.从右到左扫描各个字符，如果第从右到左扫描各个字符，如果第k个字符不是个字符不是按字典序递按字典序递增增的的，下一个排列可以将第，下一个排列可以将第k个字个字符增加一位后修改得到。符增加一位后修改得到。3.将第将第k个字符增加一位后，可能与该字符前缀个字符增加一位后，可能与该字符前缀中的字符重复，那就再增加一位，直到与前缀中的字符重复，那就再增加一位，直到与前缀中的字符不重。中的字符不重。4.若第若第k个字符增加一位后，仅与该字符后缀中个字符增加一位后，仅与该字符后缀中的字符重复，那就与后缀中重复的字符互换。的字符重复，那就与后缀中重复的字符互换。85.执行第执行第4步后，保留前缀和新的第步后，保留前缀和新的第k个字符，将个字符，将后缀的字符按字典序重新排列就得到原排列紧后缀的字符按字典序重新排列就得到原排列紧接的排列。接的排列。例例 按字典序求按字典序求839647521的下一个排列，的下一个排列，解：最大的解：最大的9-排列在最后，对于该排列，从右向排列在最后，对于该排列，从右向左找出比右边数字左找出比右边数字小小的第一个数的第一个数4，将它加，将它加1(加加后不与前缀的数字重复后不与前缀的数字重复)变成变成5；9 再对后缀从小到大重新排序再对后缀从小到大重新排序1257，修改后缀中的，修改后缀中的重复数字重复数字5为为4，接上前缀，接上前缀8396得到得到839651247，即是原排列即是原排列839647521的下一个排列的下一个排列.例例 按字典序求集合按字典序求集合a,b,c,d,e的一个的一个5-排列排列ebadc下一个排列下一个排列.解：英文字母序是：解：英文字母序是：abcde；将；将5-排列排列ebadc从右从右向左扫描，从右向左找出比右边字母向左扫描，从右向左找出比右边字母先先的第一的第一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 34 1 2 34 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 24 3 1 24 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 14 2 3 14 2 1 3 2 4 1 3 2 1 4 3 2 1 3 414考察考察4 4排列的生成过程，不难发现，按排列的生成过程，不难发现，按4的走向可的走向可 将将全全部部排排列列分分成成(4-1)！=6块块,其其中中每每一一块块的的其其余余排排列列均均可可用用前前一一排排列列交交换换4 4与与相相邻邻数数字字而而得得。对对于于1,2,n，最最后后一一个个排排列列交交换换最最后后两两个个数数字字而而得得。进进而而考考察察n(n4)排排列列的的生生成成过过程程可可知知，相相邻邻块块交交界界处处两两个个排排列列的的数数字字交交换换并并不不一一定定发发生生在在边边界界处处，而而是是按按照照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,2n，并初始化各数的并初始化各数的 方向为方向为 ；2.当当前排列中存在活动整数时，做当当前排列中存在活动整数时，做:）找出当前排列的最大活动整数）找出当前排列的最大活动整数m (可能随它的位置而发生改变可能随它的位置而发生改变)；）交换交换m和其它所指向的相邻整数；和其它所指向的相邻整数；）改变所有满足）改变所有满足pm的整数的整数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排列；排列；214 令令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.Si:=i 4.print s1,sn /打印第一个排列打印第一个排列23 5.for i:=2 to n!do 6.begin 7.m:=n-1 8.while smsm+1 do 9./从右边找到第一个减少从右边找到第一个减少 10.m:=m-1 11.k:=n 12.while smsk do 13./找到找到smsk的最右元素的最右元素 14.k:=k-124 15.swap(sm,sk)16.p:=m+1 17.q:=n 18.while pq do 19./交换交换sm+1和和sn,交换交换sm+2和和sn-1,等。等。20.begin 21.swap(sp,sq)22.p:=p+1 23.q:=q-125 24.end 25.print s1,sn/打印第打印第i个排个排列列 26.end 27.end permutation 大家可以上机运行上述程序。大家可以上机运行上述程序。26 4.2 排列中的逆序排列中的逆序 假假设设i1,i2,in是是集集合合1,2,n的的一一个个排排列列。如如果果存存在在kil则则称称数数对对(ik,il)为为该该排排列列中中的的一一个个逆逆序序(反反序序)，即即前前面面的的元元素素大大于于后后面面的元素，不一定是排列中相邻的元素，例如：的元素，不一定是排列中相邻的元素，例如：排排 列列 31524中中 有有 四四 个个 逆逆 序序，分分 别别 是是：(3,1),(3,2),(5,2),(5,4)。集集合合1,2,n的的排列中唯一没有逆序的排列是：排列中唯一没有逆序的排列是：1,2,n。27 对对于于排排列列 i1,i2,in,我我们们定定义义非非负负整整数数aj(j1,2,n)是是该该排排列列中中逆逆序序数数的的总总和和。其其中中整整数数j是是重重要要的的第第二二成成分分，并并称称aj为为整整数数j在在该该排排列列中的中的逆序数逆序数。aj表表示示了了排排列列中中的的逆逆序序数数量量，但但它它是是相相对对整整数数j来来计计算算的的，换换句句话话说说：aj等等于于在在排排列列中中先先于于 j但但大大于于j的的整整数数的的个个数数，即即j 之之前前比比j 大大的的数数的数量；它度量了的数量；它度量了j反序的反序的程度。程度。28 对于逆序数对于逆序数aj而言，自身又能够成一个数字序而言，自身又能够成一个数字序 列列：a1,a2,an;我我们们把把这这个个数数字字序序列叫做原排列列叫做原排列i1,i2,in的的逆序列逆序列。数数a1a2+an可可以以度度量量原原排排列列的的无无序序程程度度，它它的值越大，说明相应的排列的的值越大，说明相应的排列的无序程度无序程度越大。越大。例例：在在集集合合1,2,3,4,5中中有有排排列列31524，12345，54321。下下表表给给出出了了每每个个排排列列的的逆逆序序和和相相应应的逆序列：的逆序列：29 排排 列列逆逆 序序逆逆 序序 列列a1a2a3a4a53 1 5 2 4(3,1),(3,2),(5,2),(5,4)120101 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)4321030对于排列对于排列3 1 5 2 4的逆序列的逆序列a1,a2,a3,a4,a5。1前前 面面比比1大大的的数数只只有有一一个个3，a1=1;2前前面面比比2大大的的数数有有两两个个3 和和 5，a2=2;3前前面面比比3大大的的数数没没有有a3=0;4前前面面比比4大大的的数数只只有有5;a4=1;5前前面面比比5大的数没有大的数没有a5=0;故：故：a1,a2,a3,a4,a5 1,2,0,1,0 排排列列i1,i2,in的的逆逆序序列列a1,a2,an满满足足条条件：件：0 a1 n-1 (a1是是1前面并且大于前面并且大于1的数是个数的数是个数)31 0 a2 n-2 (a2是是2前面并且大于前面并且大于2的数是个数的数是个数).0 an-1 1 (an-1是是n-1前面并且大于前面并且大于n-1的数是个数的数是个数)an=0 ;这样逆序列可能构成的数量为：这样逆序列可能构成的数量为：n(n-1)(n-1)3 2 1=n!这刚好与集合这刚好与集合1,2,n的的所有排列数相同，所有排列数相同，这样就提出问题：集合这样就提出问题：集合1,2,n的的不同的排列不同的排列就有不同的逆序列。下面给予证明：就有不同的逆序列。下面给予证明：32定理定理4.2.1 令令b1，b2，bn是满足是满足 0 b1 n1；0 b2 n2；0 bn1 1；bn0 的整数序列。那么，通过的整数序列。那么，通过b1，b2，bn可可以唯一的构造出以唯一的构造出1,2,n一个序列，使得它一个序列，使得它的逆序列是：的逆序列是：b1，b2，bn。证明证明 采用两种方法唯一构造一个排列，使它采用两种方法唯一构造一个排列，使它的逆序列是的逆序列是b1，b2，bn。33 算法一算法一 从逆序列构造一个排列从逆序列构造一个排列 n:写出写出 n n-1:考虑考虑 bn-1。我们知道我们知道0bn11如果如果bn-1=0,那么那么n-1必须放在必须放在n的前面。如果的前面。如果bn-1=1,那么那么 n-1必须放在必须放在n的后面。的后面。n-2:考虑考虑 bn-2。我们知道我们知道0bn22如果如果bn-2=0,34 那么那么n-2必须放在从必须放在从n 1步得到的两个数的步得到的两个数的前面前面。如果如果bn-2=1,那么那么n-2必须放在从必须放在从n 1步得到步得到的两个数的的两个数的中间中间。如果。如果bn-2=2,那么那么n-2必须放在必须放在从从n 1步得到的两个数的步得到的两个数的后面后面。.1:我们必须把我们必须把 1 放在步骤放在步骤n-1所构成的序所构成的序列的第列的第b1个数的后面。个数的后面。35例：例：确定确定1,2,3,4,5,6,7,8的排列，已知它的的排列，已知它的逆序列是：逆序列是：5,3,4,0,2,1,1,0。解：由上面算法一，各步数插入位置后产生下列解：由上面算法一，各步数插入位置后产生下列结果：结果：8步步:8 4步步:4 8 6 5 7 7步步:8 7 3步步:4 8 6 5 3 7 6步步:8 6 7*2步步:4 8 6 2 5 3 7 5步步:8 6 5 7 1步步:4 8 6 2 5 1 3 7 因此，该逆序列的排列是：因此，该逆序列的排列是：4 8 6 2 5 1 3 736 算法二算法二 从逆序列构造一个排列从逆序列构造一个排列 从从n个空位置开始，从左到右把这些位置标个空位置开始，从左到右把这些位置标为：为：1,2,3,n。1：由于在排列中要有由于在排列中要有b1个整数在个整数在1的前面，因此的前面，因此必须把必须把1放在放在b1+1的位置上。的位置上。2：由于在排列中要有：由于在排列中要有b2个整数在个整数在2的前面，而且的前面，而且这些整数还没有被插进来，因此必须给这些整这些整数还没有被插进来，因此必须给这些整数留出数留出b2个空位置个空位置,于是把于是把2放在放在b2+1的位置上。的位置上。37 .k:(一一般般步步骤骤)由由于于在在排排列列中中要要有有bk个个整整数数在在k的的前前面面，因因此此必必须须给给这这些些整整数数留留出出bk个个空空位位置置,在在本本步步骤骤开开始始时时空空位位置置的的个个数数是是n-(k-1)=n-k+1。于是把于是把k放在从左边数的第放在从左边数的第(bk+1)的位置上的位置上 .n:把把n放在放在剩余的一个空位置上。剩余的一个空位置上。例例：(还还是是上上题题)确确定定1,2,3,4,5,6,7,8的的排排列列，已知它的逆序列是：已知它的逆序列是：5,3,4,0,2,1,1,0。381步步12步步213步步2134步步42135步步425136步步4625137步步46251378步步48625137位置位置一一二二三三四四五五六六七七八八解解:由上面算法二由上面算法二,分别将数插入位置后得到结果分别将数插入位置后得到结果:逆序列逆序列5,3,4,0,2,1,1,0的排列是：的排列是：4 8 6 2 5 1 3 739 通过上面的证明我们可以看出，一个排列可通过上面的证明我们可以看出，一个排列可 以以通通过过指指定定它它的的逆逆序序列列而而唯唯一一确确定定。逆逆序序列列可以看成排列的可以看成排列的“代码代码”这种功能多用于这种功能多用于编码编码。习习惯惯上上。按按照照其其逆逆序序个个数数的的偶偶数数或或者者奇奇数数而而把把1,2,n 的的排排列列 i1,i2,in称称为为偶偶的的或或奇奇的的。排排列列的的符符号号按按照照偶偶的的或或奇奇的的而而被被定定义义为为+1或或-1。排排列列的的符符号号在在矩矩阵阵的的行行列列式式理理论论中中很很重重要要。我我们们不需要更进一步讨论。不需要更进一步讨论。40总总 结结 本本次课次课我们介绍了自然数集合生成排列我们介绍了自然数集合生成排列的方法以及排列数和逆序列等，逆序列与的方法以及排列数和逆序列等，逆序列与排列的关系多用与编码技术方面。排列的关系多用与编码技术方面。要求能生成排列，能求出排列的逆序列，要求能生成排列，能求出排列的逆序列，能通过排列的逆序列求出排列。能通过排列的逆序列求出排列。41本次授课到此结束本次授课到此结束作业如下作业如下:P72 2,6,7，102.确定在确定在 中的活动整数。中的活动整数。6.确定确定1,2,3,.,8的下列排列的逆序列。的下列排列的逆序列。427.构造构造1,2,3,.,8的排列，其逆序列是的排列，其逆序列是10.通过逐次交换相邻的数把排列通过逐次交换相邻的数把排列256143和和436251变成变成123456。下次上课内容：下次上课内容：4.3 生成生成组合组合43