生成排列和組合1

1

一、生成排列

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

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

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

3,4,5,1,2;刪去5后得到3,4,1,2;這個四個數(shù)的排列剛好也可以從{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、字典序法對給定的字符集中的字符規(guī)定了一個先后關系，在此基礎上規(guī)定兩個全排列的先后是從左到右逐個比較對應的字符的先后，數(shù)字按由小到大、字母按英文字母表順序。例字符集{1,2,3},按較小的數(shù)字較先,生成的全排列按字典序的順序是:(123),(132),(213),(231),(312),(321)

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

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

23和1

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

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

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

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

再對后綴從小到大重新排序1257，修改后綴中的重復數(shù)字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排列的生成過程，不難發(fā)現(xiàn)，按4的走向可將全部排列分成(4-1)！=6塊,其中每一塊的其余排列均可用前一排列交換4與相鄰數(shù)字而得。對于1,2,…n，最后一個排列交換最后兩個數(shù)字而得。進而考察n(n＞4)排列的生成過程可知，相鄰塊交界處兩個排列的數(shù)字交換并不一定發(fā)生在邊界處，而是按照n-1排列的生成順序交換相鄰數(shù)字。12

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

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

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

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

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

1.構造第一個排列1,2…n，并初始化各數(shù)的方向為；

2.當前排列中存在活動整數(shù)時，做:?。┱页霎斍芭帕械淖畲蠡顒诱麛?shù)m(可能隨它的位置而發(fā)生改變)；

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

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

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