生成排列和组合1

1

一、生成排列

本节课我们将讨论排列和组合的某些排序方案以及执行这些方案的算法。

由前面知识可知，n个正整数组成的集合：{1,2,3,….n}有n!个排列，只要n稍大，n!的值也很大，例如15!比1000000000000还大。

例如：我们从{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}的排列。25,3,4,1,23,5,4,1,23,4,5,1,23,4,1,5,23,4,1,2,5这里介绍全排列两种算法：

(A)字典序法(B)错位置排法

1、字典序法对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后，数字按由小到大、字母按英文字母表顺序。例字符集{1,2,3},按较小的数字较先,生成的全排列按字典序的顺序是:(123),(132),(213),(231),(312),(321)

这六个三位数是按由小到大的顺序排列的。※※

一个全排列可看做一个字符串，字符串可以有前缀、后缀。例如1

23和1

323生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。例：839647521是1--9的排列。1--9的排列最前面的是123456789，也是1--9的排列中数值最小的；最后面的是987654321，也是1--9的排列中数值最大的；从右向左扫描若都是增的，就到了987654321，也就没有下一个了。45

我们对一个给定的排列寻找按字典序紧接的下一个排列，就是要尽可能保留长的共同前缀，而去修改不同的字符和后缀。我们给出这样一种方法：

1.对给定的排列，从右到左扫描各个字符，如果这些字符从右到左是按字典序递增的，该排列就是最后一个，没有下一个排列。62.从右到左扫描各个字符，如果第k个字符不是按字典序递增的，下一个排列可以将第k个字符增加一位后修改得到。3.将第k个字符增加一位后，可能与该字符前缀中的字符重复，那就再增加一位，直到与前缀中的字符不重。4.若第k个字符增加一位后，仅与该字符后缀中的字符重复，那就与后缀中重复的字符互换。75.保留前缀和新的第k个字符，将后缀的字符按字典序重新排列就得到原排列紧接的排列。例按字典序求839647521的下一个排列。解：最大的9-排列在最后，对于该排列，从右向左找出比右边数字小的第一个数4，将它加1(加后不与前缀的数字重复)变成5；

再对后缀从小到大重新排序1257，修改后缀中的重复数字5为4，接上前缀8396得到839651247，即是原排列839647521的下一个排列.

再对后缀从小到大重新排序1257，修改后缀中的重复数字5为4，接上前缀8396得到839651247，即是原排列839647521的下一个排列.例按字典序求集合{a,b,c,d,e}的一个5-排列ebadc下一个排列.

解：英文字母序是：abcde；将5-排列ebadc从右向左扫描，从右向左找出比右边字母先的第一89

个字母a

，将它增加1位变成b后与前缀中的字母重复，再将它增加1位变成c后不与前缀中的字母重复，保留前缀eb将a换成c，把后缀dc中的重复字母c换成a，对新后缀按字典序重新排列成ad；即得到新的排列是:ebcad

；这个排列就是紧接着5-排列ebadc最近的一个排列。

二、

错位排法（1）当n=1，排列方式只有一种，就是1。（2）当n=2时，先将惟一的1-排列1写出两次，并错位置插入2，即得两个2-排列如下：101221（3）当n=3时，先将两块2-排列分别写出3次，并错位置插入3，即得3!=6个3排列如右（4）当n=4时,先将6块3-排列分别写出4次,并错位置以4,即得4!=24个4排列。

12341243142341234

132

1

4

32

13

4

2

132

411

31243142341243124

32134213241321

4

23142341243142314

213

2

4

13

21

4

3

213

4考察4排列的生成过程，不难发现，按4的走向可将全部排列分成(4-1)！=6块,其中每一块的其余排列均可用前一排列交换4与相邻数字而得。对于1,2,…n，最后一个排列交换最后两个数字而得。进而考察n(n＞4)排列的生成过程可知，相邻块交界处两个排列的数字交换并不一定发生在边界处，而是按照n-1排列的生成顺序交换相邻数字。12

求n排列时，不用保存(n-1)!个n-1排列，而只需要利用一个n位长的一维数组存放一个n排列，然后每次对它交换某相邻数据产生下一个n排列。求算过程中，每产生一个n排列，即行输出，输出不能集中到最后。因为只给出了一个排列的存储空间，后边的结果会代替前边的结果。13

给定一个整数k，我们用或表示k具有向右或向左的方向。在{1,2,…,n}的一个排列中，若每个整数均具有指定的方向，且若某个整数k的方向所指的k的相邻元素比k小，则称k在该排列中是活动的。例如，对于排列：其中6,3,5是活动的,因为6,3,5右边的数比自己小。14一个排列中所有活动整数的最大者称为该排列的最大活动整数。例如，上述例子中6是最大活动整数。由此可知，{1,2,3,….n}的排列中，1是不可能活动的，除下列两种情况外，n总是活动的。

1)n是第一个整数而且它的箭头指向左：

2)n是最后一个整数而且它的箭头指向右：15下面我们给出生成所有排列的算法：

0.输正整数n；

1.构造第一个排列1,2…n，并初始化各数的方向为；

2.当前排列中存在活动整数时，做:ⅰ）找出当前排列的最大活动整数m(可能随它的位置而发生改变)；

ⅱ）交换m和其它所指向的相邻整数；

ⅲ）改变所有满足p>m的整数p的方向；

ⅳ）以上处理的结果生成了一个新的排列16我们就n=4叙述该算法。结果用三列显示：17由于在中除4外没有活动整数，算法终止。·对错位置数生成n！个全排列的改进算法№1对某个选中的n-1排列，置n于最右端得到一个n排列；№2令n由右向左与相邻数字交换，每交换一次即得一个n排列(共可得n-1个n排列)；№3当n到达最左端时，若n!个n排列均已生成，转№7；否则，令除n以外的数n-1按№2交换最大数字相邻的数字，得到下一个n-1排列，连同最左端的