生成排列和組合1

1

一、生成排列

本節(jié)課我們將討論排列和組合的某些排序方案以及執(zhí)行這些方案的算法。

由前面知識可知，n個(gè)正整數(shù)組成的集合：{1,2,3,….n}有n!個(gè)排列，只要n稍大，n!的值也很大，例如15!比1000000000000還大。

例如：我們從{1,2,3,…5}的排列中任意找一個(gè)

3,4,5,1,2;刪去5后得到3,4,1,2;這個(gè)四個(gè)數(shù)的排列剛好也可以從{1,2,3,4}的排列中得到。它們的關(guān)系如右：反之,求{1,2,3,….n}的排列也可以先求{1,2….n-1}的排列再把n插在各個(gè)元素之間而得到

{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)錯(cuò)位置排法

1、字典序法對給定的字符集中的字符規(guī)定了一個(gè)先后關(guān)系，在此基礎(chǔ)上規(guī)定兩個(gè)全排列的先后是從左到右逐個(gè)比較對應(yīng)的字符的先后，數(shù)字按由小到大、字母按英文字母表順序。例字符集{1,2,3},按較小的數(shù)字較先,生成的全排列按字典序的順序是:(123),(132),(213),(231),(312),(321)

這六個(gè)三位數(shù)是按由小到大的順序排列的。※※

一個(gè)全排列可看做一個(gè)字符串，字符串可以有前綴、后綴。例如1

23和1

323生成給定全排列的下一個(gè)排列所謂一個(gè)的下一個(gè)就是這一個(gè)與下一個(gè)之間沒有其他的。這就要求這一個(gè)與下一個(gè)有盡可能長的共同前綴，也即變化限制在盡可能短的后綴上。例：839647521是1--9的排列。1--9的排列最前面的是123456789，也是1--9的排列中數(shù)值最小的；最后面的是987654321，也是1--9的排列中數(shù)值最大的；從右向左掃描若都是增的，就到了987654321，也就沒有下一個(gè)了。45

我們對一個(gè)給定的排列尋找按字典序緊接的下一個(gè)排列，就是要盡可能保留長的共同前綴，而去修改不同的字符和后綴。我們給出這樣一種方法：

1.對給定的排列，從右到左掃描各個(gè)字符，如果這些字符從右到左是按字典序遞增的，該排列就是最后一個(gè)，沒有下一個(gè)排列。62.從右到左掃描各個(gè)字符，如果第k個(gè)字符不是按字典序遞增的，下一個(gè)排列可以將第k個(gè)字符增加一位后修改得到。3.將第k個(gè)字符增加一位后，可能與該字符前綴中的字符重復(fù)，那就再增加一位，直到與前綴中的字符不重。4.若第k個(gè)字符增加一位后，僅與該字符后綴中的字符重復(fù)，那就與后綴中重復(fù)的字符互換。75.保留前綴和新的第k個(gè)字符，將后綴的字符按字典序重新排列就得到原排列緊接的排列。例按字典序求839647521的下一個(gè)排列。解：最大的9-排列在最后，對于該排列，從右向左找出比右邊數(shù)字小的第一個(gè)數(shù)4，將它加1(加后不與前綴的數(shù)字重復(fù))變成5；

再對后綴從小到大重新排序1257，修改后綴中的重復(fù)數(shù)字5為4，接上前綴8396得到839651247，即是原排列839647521的下一個(gè)排列.

再對后綴從小到大重新排序1257，修改后綴中的重復(fù)數(shù)字5為4，接上前綴8396得到839651247，即是原排列839647521的下一個(gè)排列.例按字典序求集合{a,b,c,d,e}的一個(gè)5-排列ebadc下一個(gè)排列.

解：英文字母序是：abcde；將5-排列ebadc從右向左掃描，從右向左找出比右邊字母先的第一89

個(gè)字母a

，將它增加1位變成b后與前綴中的字母重復(fù)，再將它增加1位變成c后不與前綴中的字母重復(fù)，保留前綴eb將a換成c，把后綴dc中的重復(fù)字母c換成a，對新后綴按字典序重新排列成ad；即得到新的排列是:ebcad

；這個(gè)排列就是緊接著5-排列ebadc最近的一個(gè)排列。

二、

錯(cuò)位排法（1）當(dāng)n=1，排列方式只有一種，就是1。（2）當(dāng)n=2時(shí)，先將惟一的1-排列1寫出兩次，并錯(cuò)位置插入2，即得兩個(gè)2-排列如下：101221（3）當(dāng)n=3時(shí)，先將兩塊2-排列分別寫出3次，并錯(cuò)位置插入3，即得3!=6個(gè)3排列如右（4）當(dāng)n=4時(shí),先將6塊3-排列分別寫出4次,并錯(cuò)位置以4,即得4!=24個(gè)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排列的生成過程，不難發(fā)現(xiàn)，按4的走向可將全部排列分成(4-1)！=6塊,其中每一塊的其余排列均可用前一排列交換4與相鄰數(shù)字而得。對于1,2,…n，最后一個(gè)排列交換最后兩個(gè)數(shù)字而得。進(jìn)而考察n(n＞4)排列的生成過程可知，相鄰塊交界處兩個(gè)排列的數(shù)字交換并不一定發(fā)生在邊界處，而是按照n-1排列的生成順序交換相鄰數(shù)字。12

求n排列時(shí)，不用保存(n-1)!個(gè)n-1排列，而只需要利用一個(gè)n位長的一維數(shù)組存放一個(gè)n排列，然后每次對它交換某相鄰數(shù)據(jù)產(chǎn)生下一個(gè)n排列。求算過程中，每產(chǎn)生一個(gè)n排列，即行輸出，輸出不能集中到最后。因?yàn)橹唤o出了一個(gè)排列的存儲(chǔ)空間，后邊的結(jié)果會(huì)代替前邊的結(jié)果。13

給定一個(gè)整數(shù)k，我們用或表示k具有向右或向左的方向。在{1,2,…,n}的一個(gè)排列中，若每個(gè)整數(shù)均具有指定的方向，且若某個(gè)整數(shù)k的方向所指的k的相鄰元素比k小，則稱k在該排列中是活動(dòng)的。例如，對于排列：其中6,3,5是活動(dòng)的,因?yàn)?,3,5右邊的數(shù)比自己小。14一個(gè)排列中所有活動(dòng)整數(shù)的最大者稱為該排列的最大活動(dòng)整數(shù)。例如，上述例子中6是最大活動(dòng)整數(shù)。由此可知，{1,2,3,….n}的排列中，1是不可能活動(dòng)的，除下列兩種情況外，n總是活動(dòng)的。

1)n是第一個(gè)整數(shù)而且它的箭頭指向左：

2)n是最后一個(gè)整數(shù)而且它的箭頭指向右：15下面我們給出生成所有排列的算法：

0.輸正整數(shù)n；

1.構(gòu)造第一個(gè)排列1,2…n，并初始化各數(shù)的方向?yàn)椋?/p>

2.當(dāng)前排列中存在活動(dòng)整數(shù)時(shí)，做:?。┱页霎?dāng)前排列的最大活動(dòng)整數(shù)m(可能隨它的位置而發(fā)生改變)；

ⅱ）交換m和其它所指向的相鄰整數(shù)；

ⅲ）改變所有滿足p>m的整數(shù)p的方向；

ⅳ）以上處理的結(jié)果生成了一個(gè)新的排列16我們就n=4敘述該算法。結(jié)果用三列顯示：17由于在中除4外沒有活動(dòng)整數(shù)，算法終止?！﹀e(cuò)位置數(shù)生成n！個(gè)全排列的改進(jìn)算法№1對某個(gè)選中的n-1排列，置n于最右端得到一個(gè)n排列；№2令n由右向左與相鄰數(shù)字交換，每交換一次即得一個(gè)n排列(共可得n-1個(gè)n排列)；№3當(dāng)n到達(dá)最左端時(shí)，若n!個(gè)n排列均已生成，轉(zhuǎn)№7；否則，令除n以外的數(shù)n-1按№2交換最大數(shù)字相鄰的數(shù)字，得到下一個(gè)n-1排列，連同最左端的