




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
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}的排列中得到。它們的關(guān)系如右:反之,求{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ān)系,在此基礎(chǔ)上規(guī)定兩個全排列的先后是從左到右逐個比較對應(yīng)的字符的先后,數(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個字符增加一位后,可能與該字符前綴中的字符重復(fù),那就再增加一位,直到與前綴中的字符不重。4.若第k個字符增加一位后,僅與該字符后綴中的字符重復(fù),那就與后綴中重復(fù)的字符互換。75.保留前綴和新的第k個字符,將后綴的字符按字典序重新排列就得到原排列緊接的排列。例按字典序求839647521的下一個排列。解:最大的9-排列在最后,對于該排列,從右向左找出比右邊數(shù)字小的第一個數(shù)4,將它加1(加后不與前綴的數(shù)字重復(fù))變成5;
再對后綴從小到大重新排序1257,修改后綴中的重復(fù)數(shù)字5為4,接上前綴8396得到839651247,即是原排列839647521的下一個排列.
再對后綴從小到大重新排序1257,修改后綴中的重復(fù)數(shù)字5為4,接上前綴8396得到839651247,即是原排列839647521的下一個排列.例按字典序求集合{a,b,c,d,e}的一個5-排列ebadc下一個排列.
解:英文字母序是:abcde;將5-排列ebadc從右向左掃描,從右向左找出比右邊字母先的第一89
個字母a
,將它增加1位變成b后與前綴中的字母重復(fù),再將它增加1位變成c后不與前綴中的字母重復(fù),保留前綴eb將a換成c,把后綴dc中的重復(fù)字母c換成a,對新后綴按字典序重新排列成ad;即得到新的排列是:ebcad
;這個排列就是緊接著5-排列ebadc最近的一個排列。
二、
錯位排法(1)當(dāng)n=1,排列方式只有一種,就是1。(2)當(dāng)n=2時,先將惟一的1-排列1寫出兩次,并錯位置插入2,即得兩個2-排列如下:101221(3)當(dāng)n=3時,先將兩塊2-排列分別寫出3次,并錯位置插入3,即得3!=6個3排列如右(4)當(dāng)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ù)字而得。進(jìn)而考察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排列,即行輸出,輸出不能集中到最后。因為只給出了一個排列的存儲空間,后邊的結(jié)果會代替前邊的結(jié)果。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.構(gòu)造第一個排列1,2…n,并初始化各數(shù)的方向為;
2.當(dāng)前排列中存在活動整數(shù)時,做:ⅰ)找出當(dāng)前排列的最大活動整數(shù)m(可能隨它的位置而發(fā)生改變);
ⅱ)交換m和其它所指向的相鄰整數(shù);
ⅲ)改變所有滿足p>m的整數(shù)p的方向;
ⅳ)以上處理的結(jié)果生成了一個新的排列16我們就n=4敘述該算法。結(jié)果用三列顯示:17由于在中除4外沒有活動整數(shù),算法終止?!﹀e位置數(shù)生成n!個全排列的改進(jìn)算法№1對某個選中的n-1排列,置n于最右端得到一個n排列;№2令n由右向左與相鄰數(shù)字交換,每交換一次即得一個n排列(共可得n-1個n排列);№3當(dāng)n到達(dá)最左端時,若n!個n排列均已生成,轉(zhuǎn)№7;否則,令除n以外的數(shù)n-1按№2交換最大數(shù)字相鄰的數(shù)字,得到下一個n-1排列,連同最左端的
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 民用建筑工程室內(nèi)環(huán)境污染治理合作協(xié)議合同
- 跨國軟件許可合作合同:知識產(chǎn)權(quán)保護(hù)
- 度建筑幕墻工程分包合同
- 承包香梨園合同范本
- 物業(yè)拎包入住合同范本
- ktv接手轉(zhuǎn)讓合同范本
- 辦公場地管理服務(wù)合同范例
- 出口股合同范例
- 公園草坪綠化養(yǎng)護(hù)合同范例
- 下鄉(xiāng)演出合同范例
- 豪邁CutRite V9板材優(yōu)化軟件學(xué)習(xí)教材
- GB 2715-2016食品安全國家標(biāo)準(zhǔn)糧食
- 深圳市失業(yè)人員停止領(lǐng)取失業(yè)保險待遇申請表樣表
- 建設(shè)工程合同糾紛-審判實(shí)務(wù)分析課件
- 門診慢特病病種待遇認(rèn)定申請表
- 滅火器檢查卡
- 《IP地址和域名》-高中信息技術(shù)人教-中圖版(2019)必修2
- 南站二期標(biāo)識設(shè)計變更003精神堡壘施工圖
- JIS G4305-2021 冷軋不銹鋼板材、薄板材和帶材
- 自我探索價值觀講課稿
- 園林工程計量與計價PPT全套課件
評論
0/150
提交評論