參考教案成果2013-permutation

1、1 Combinatorics第一章 排列與組合馬昱春MA Yuchun 12內(nèi)容回顧加法法則和乘法法則排列從n個(gè)不同的球中,取出r個(gè),放入r個(gè)不同的盒子里,每盒1個(gè)。P(n,r) = n(n-1)(n-r+1) = 組合從n個(gè)不同的球中,取出r個(gè),放入r個(gè)相同的盒子里,每盒1個(gè)。C(n,r) = P(n,r)/r! = 模型轉(zhuǎn)換21.4 全排列的生成算法全排列的生成算法：就是對(duì)于給定的字符集，用有效的方法將所有可能的全排列無重復(fù)無遺漏地枚舉出來。問題的提出：1.排列組合搜索：“我” “是” “馬昱春”三個(gè)詞組的排列排列數(shù)： 3! = 6需要列出所有的排列來實(shí)現(xiàn)對(duì)三個(gè)詞組的組合檢索”我是馬昱春

2、” “我 馬昱春 是” “是 馬昱春 我” “是我馬昱春” “馬昱春 我是” “馬昱春 是我” 2.在旅行商問題中，如何列出所有的方案，找到其中代價(jià)最小的?3. 彩票中的排列4. 測(cè)試向量的生成？3Generating PermutationsCan we start from the simple thing first?The permutation of 1 1The permutation of 1 2 1 2 2 1The permutation of 1 2 3 1221 23332 13333332 12 12 11 21 21 2333Generate the permutat

3、ions of 1,2,n based on the permutations of 1,2,n-1InductionHigh complexity!Waste of memory!4全排列的生成算法任何n個(gè)字符集的排列都可以與1-n的n個(gè)數(shù)字的排列一一對(duì)應(yīng)，n個(gè)數(shù)字的全體排列之間存在一個(gè)確定的線性順序關(guān)系。“abc”的下一個(gè)排列是 “acb” 所有的排列中除最后一個(gè)排列外，都有一個(gè)后繼；除第一個(gè)排列外，都有一個(gè)前驅(qū)。每個(gè)排列的后繼都可以從它的前驅(qū)經(jīng)過最少的變化而得到全排列的生成算法就是從第一個(gè)排列開始逐個(gè)生成所有的排列的方法。5abcacbbaccabcbabca1.5.1字典序法對(duì)給定的字

4、符集中的字符規(guī)定了一個(gè)先后關(guān)系，在此基礎(chǔ)上規(guī)定兩個(gè)全排列的先后是從左到右逐個(gè)比較對(duì)應(yīng)的字符的先后。例字符集1,2,3,較小的數(shù)字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321。一個(gè)全排列可看做一個(gè)字符串，字符串可有前綴、后綴。生成給定全排列的下一個(gè)排列所謂一個(gè)的下一個(gè)就是這一個(gè)與下一個(gè)之間沒有其他的。這就要求這一個(gè)與下一個(gè)有盡可能長(zhǎng)的共同前綴，也即變化限制在盡可能短的后綴上。6這就要求這一個(gè)與下一個(gè)有盡可能長(zhǎng)的共同前綴，也即變化限制在盡可能短的后綴上。123,132,213,231,312,321。從右向左掃描都是增的，就不存在下一個(gè);要找第一次出現(xiàn)下降的位置

5、;2 1 31.5.1字典序法71 2 3?3 2 11 3 2交換？最小的換后面的2 3 1后綴最小比1大的例求839647521的下一個(gè)排列1 先找從右到左第一次出現(xiàn)下降的位置42.交換：3.將后綴翻轉(zhuǎn)得到下一個(gè)排列是83965124783964752183965742112478396475218找后綴中比4大的最小的數(shù)設(shè)P是1n的一個(gè)全排列: P = p1p2.pn = p1p2.pj-1pjpj+1.pk-1pkpk+1.pn1）從排列的右端開始，找出第一個(gè)比右邊數(shù)字小的數(shù)字的序號(hào)j（j從左端開始計(jì)算），即 j=maxi|pipj（右邊的數(shù)從右至左是遞增的，因此k是所有大于pj的數(shù)字

6、中序號(hào)最大者）3）對(duì)換pi，pk 4）再將pj+1.pk-1pkpk+1.pn倒轉(zhuǎn)得到排列p=p1p2.pj-1pjpn.pk+1pkpk-1.pj+1，這就是排列P的下一個(gè)下一個(gè)排列。83964752183964752183965742112479計(jì)算給定排列的序號(hào)全排列的序號(hào)即先于此排列的排列的個(gè)數(shù)。將先于此排列的排列按前綴分類。前綴先于8的排列的個(gè)數(shù)：78!1*，2*，7*第一位是8,先于83的排列的個(gè)數(shù)：27!82*,81*前4位是8396,先于83964得的排列的個(gè)數(shù)：24!前5位是83964,先于839647得的排列的個(gè)數(shù)：33!前6位是839647,先于8396475得的排列的個(gè)

7、數(shù)：22!前3位是839,先于8396得的排列的個(gè)數(shù)：45!前7位是8396475,先于83964752得的排列的個(gè)數(shù)：11!前2位是83,先于839的排列的個(gè)數(shù)：66!831*,832*,834*,835*,836*,837*78!+27!+66!+45!+24!+33!+22!+11!= 297191即839647521的序號(hào)是 297191，表明839647521前面有297191個(gè)排列83964752110123, 132, 213, 231, 312, 321 0 1 2 3 4 5312的序號(hào)是？1.5.1字典序法將8!,7!,1!前面的系數(shù)抽出，放在一起得到 72642321中介

8、數(shù)的特點(diǎn)：記錄當(dāng)前數(shù)字右邊比當(dāng)前數(shù)字小的數(shù)字的個(gè)數(shù) 72642321是計(jì)算排列839647521的序號(hào)的中間環(huán)節(jié)，稱之為中介數(shù)。78!+27!+66!+45!+24!+33!+22!+11!中介數(shù)，序號(hào)和排列之間是一一對(duì)應(yīng)的關(guān)系。序號(hào)是十進(jìn)制的數(shù)，如何從序號(hào)得到排列呢？需要利用中介數(shù)，來構(gòu)造排列。839647521前3位是839,先于8396的排列的個(gè)數(shù)：45!8391*, 8392*, 8394*, 8395*左邊前綴用掉了3，因此右邊比6小的數(shù)字是5-1=4個(gè)11構(gòu)造中介數(shù) 7：8的右邊比8小的數(shù)的個(gè)數(shù) 2：3的右邊比3小的數(shù)的個(gè)數(shù)6：9的右邊比9小的數(shù)的個(gè)數(shù)4：6的右邊比6小的數(shù)的個(gè)數(shù)2

9、：4的右邊比4小的數(shù)的個(gè)數(shù)3：7的右邊比7小的數(shù)的個(gè)數(shù)2：5的右邊比5小的數(shù)的個(gè)數(shù)1：2的右邊比2小的數(shù)的個(gè)數(shù)中介數(shù)的特點(diǎn)：記錄當(dāng)前數(shù)字右邊比當(dāng)前數(shù)字小的數(shù)字的個(gè)數(shù)839647521778!+27!+66!+45!+24!+33!+22!+11!839647521728396475217268396475217264中介數(shù)記錄了排列中每位數(shù)字的排列結(jié)構(gòu)，因此可以用來構(gòu)造對(duì)應(yīng)的排列。 12由中介數(shù)推出排列的算法例 由72642321推算出839647521方法1：P1 P2 P3 P4 P5 P6 P7 P8 P9_ _ _ _ _ _ _ _ _87+1=8 P1 = 82+1=3 P2 =

10、336+1=7，但3小于7已在P3左邊出現(xiàn)，7+1=8，但8已在P3左邊出現(xiàn)，8+1=9 P3=994+1=5，但3已經(jīng)在P4左邊出現(xiàn)，5+1=6 P4=662+1=3，但3已經(jīng)在P5左邊出現(xiàn)，3+1=4 P4=44751+1=2 P8=2 P9=1 2 1中介數(shù)的特點(diǎn)：記錄當(dāng)前數(shù)字右邊比當(dāng)前數(shù)字小的數(shù)字的個(gè)數(shù)3+1=4，但3,4已經(jīng)在P6左邊出現(xiàn)，4+1+1=6，但6已經(jīng)在P6左邊出現(xiàn)， 6+1=7 P6=72+1=3，但3已經(jīng)在P7左邊出現(xiàn)，3+1=4，但4已經(jīng)在P7左邊出現(xiàn)， 4+1=5 P7=51314打點(diǎn)法算中介數(shù)從1-9定位，左邊比當(dāng)前數(shù)字大的每個(gè)數(shù)打點(diǎn)，最終，點(diǎn)的個(gè)數(shù)意味著右邊有

11、多少數(shù)比該數(shù)小 8 1 9 6 4 7 5 3 21 02 0 0 0 0 0 0 03 0 0 0 0 0 04 0 0 05 0 0 0 06 0 0 7 0 0 8 9 7 0 6 4 2 3 2 1 每個(gè)右邊的數(shù)都給左邊的大數(shù)貢獻(xiàn)一個(gè)點(diǎn)141.5.1字典序法0對(duì)應(yīng)的位置，1在最右邊打點(diǎn)法：從1-9依次定位，利用點(diǎn)來表示對(duì)應(yīng)位上的數(shù)是否比當(dāng)前數(shù)大，點(diǎn)數(shù)和當(dāng)前中介數(shù)相等的最左邊那一位即當(dāng)前數(shù)所在位置中介數(shù)右端加一個(gè)0擴(kuò)成9位每定一位，其左邊未定位下加一點(diǎn)從（位位下點(diǎn)數(shù)=0）的位中選最左的。7 2 6 4 2 3 2 1定 1 的位置1 2 3上述算法從左到右依次推出中介數(shù)。依次定出1,2,

12、3,9的位置。7 2 6 4 2 3 2 1 01定 2 的位置1的下面位位下點(diǎn)數(shù)=0 27 2 6 4 2 3 2 1 01定 3 的位置2的下面最左面位位下點(diǎn)數(shù)=015016打點(diǎn)法打點(diǎn)法：從1-9依次定位，點(diǎn)數(shù)和當(dāng)前中介數(shù)相等的最左邊那一位即當(dāng)前數(shù)所在位置中介數(shù)右端加一個(gè)0擴(kuò)成9位。從（位位下點(diǎn)數(shù)=0）的位中選最左的。每定一位，其左邊未定位下加一點(diǎn)。 7 0 6 4 2 3 2 1 02 03 0 0 0 0 0 0 04 0 0 0 0 0 05 0 0 06 0 0 0 07 0 0 8 0 0 123456789定 1 的位置：最左0的下面位位下點(diǎn)數(shù)=0定 2的位置： 0的下面位位下

13、點(diǎn)數(shù)=0定 3的位置：1的下面位位下點(diǎn)數(shù)=0定 4 的位置：2的下面位位下點(diǎn)數(shù)=0定 5的位置：2的下面位位下點(diǎn)數(shù)=0定 6的位置：4的下面位位下點(diǎn)數(shù)=0定 7的位置：3的下面位位下點(diǎn)數(shù)=0定 8的位置：7的下面位位下點(diǎn)數(shù)=01617字典序下的對(duì)應(yīng)關(guān)系排列：P=P1P2Pn n-1序號(hào)：ki(n-i)! i=1中介數(shù)：k1k2kn-11230(00)1321(01)321n!-1=5 (21)=2*2!+1*1!=5共有n!個(gè)排列0到(n!-1)0到(n!-1)個(gè)中介數(shù)中介數(shù)的特點(diǎn)：記錄當(dāng)前數(shù)字右邊比當(dāng)前數(shù)字小的數(shù)字的個(gè)數(shù)17歸納法證明n-1kk! = n!-1k=11819排列：P=P1P2

14、Pn n-1序號(hào)：ki(n-i)! i=1中介數(shù)：k1k2kn-11230(00)1321(01)321n!-1=5 (21)=2*2!+1*1!=5共有n!個(gè)排列0到(n!-1)0到(n!-1)個(gè)中介數(shù)字典序中中介數(shù)：記錄當(dāng)前數(shù)字右邊比當(dāng)前數(shù)字小的數(shù)字的個(gè)數(shù)19ki最大值是n-i序號(hào)+1 中介數(shù)？0 123 (00) 2 213 (10)3 231 (11) 4 312 (20) 5 321 (21)78!+27!+66!+45!+24!+33!+22!+11!2105+9104+7103+1102+9101+1100十進(jìn)制數(shù) 進(jìn)位制/位置計(jì)數(shù)法是一種記數(shù)方式，故亦稱進(jìn)位記數(shù)法/位值計(jì)數(shù)法，

15、可以用有限的數(shù)字符號(hào)代表所有的數(shù)值?？墒褂脭?shù)字符號(hào)的數(shù)目稱為基數(shù)(radix)或底數(shù)，基數(shù)為n，即可稱n進(jìn)位制，簡(jiǎn)稱n進(jìn)制?，F(xiàn)在最常用的是十進(jìn)制，還有二進(jìn)制，十六進(jìn)制，八進(jìn)制，甚至是七進(jìn)制。 進(jìn)制中的基數(shù)一定是固定大小的嗎？遞增進(jìn)位制數(shù)遞增/遞減進(jìn)位制數(shù) 遞增進(jìn)位制和遞減進(jìn)位制數(shù)字是指數(shù)字的進(jìn)制隨著數(shù)字位置的不同遞增或遞減。 遞增進(jìn)位制數(shù)4121，它的進(jìn)制從右向左依次是2、3、4、5即其最高位（就是數(shù)字4那位）最大可能是4；第三高位最大可能是3；第二高位最大可能是2；最末位最大可能是1 (4121) + 1 = 420021遞增進(jìn)位制數(shù)遞增進(jìn)位制數(shù)(a9 a8 a7 a6 a5 a4 a3 a

16、2 )為：a9*8! + a8*7! + .+ a3*2! + a2*1! = 序號(hào)= a9*8) + a8)*7 + .+ a3)*2 + a2)*1! 表示范圍遞增進(jìn)位制數(shù)的87654321對(duì)應(yīng)十進(jìn)制序號(hào)362879（即9!-1） 加減法：注意進(jìn)位不同72642321 = 72652011每位大于當(dāng)前位的進(jìn)制則進(jìn)位172642321 4020 = 72633301被減數(shù)當(dāng)前位不夠減，則從上一位借相應(yīng)本位的進(jìn)制大小 9 8 7 6 5 4 3 2 9 8 7 6 5 4 3 222序號(hào)轉(zhuǎn)化為遞增進(jìn)位制數(shù)a9*8! + a8*7! + .+ a3*2! + a2*1! = 序號(hào)將一個(gè)序號(hào)轉(zhuǎn)換成

17、其遞增進(jìn)位制數(shù)首先需要找到一個(gè)比序號(hào)小的最大階乘數(shù)（即1、2、6、24、120、720），對(duì)其進(jìn)行整數(shù)除得到遞增進(jìn)位制的第一位；將除法的余數(shù)反復(fù)應(yīng)用這個(gè)方法（當(dāng)然，之后選擇的余數(shù)是小一級(jí)的階乘數(shù)），直到余數(shù)為0。序號(hào)100的遞增進(jìn)位制數(shù)就是4020，即4*4！+ 0*3！+ 2*2！+ 0*1！=100 4!1003)3132Mobile IntegerGiven an integer k we assign a direction to it by writing an arrow above it pointing to the left or to the right. Consider

18、 a permutation of 1,2,n in which each of the integers is given a direction.The integer k is called mobile if its arrow points to a smaller integer adjacent to it.Integer 1 can never be mobile since there is no integer smaller than 1. The integer n is always mobile, except in two cases:n is the first

19、 integer and its arrow points to the left.n is the last integer and its arrow points to the right.only 3, 5, and 6 are mobile.XX32Generating PermutationsThe permutation of 1 2 3 4 41 2 31 2 3 2 31 2 31 3 21 3 2 3 21 3 24444444Each permutation other than the first one is obtained from the preceding o

20、ne by switching two adjacent numbers.Move the largest number 4 between two endsWhen the end is met, the largest number 4 will be fixed for a step and the switching of the second largest number 3 makes 4 movable again.Step 0: All mobileStep 1: Choose the largest mobile integer 4Step 2: Switch 4 and 3

21、 as the arrow points to.Step i: 4 is fixed, the largest mobile integer is 3. After the switch between 3 and 2, switch the direction of the arrow above 4( 43)3334Switching MethodBegin with While there exists a mobile integer, dofind the largest mobile integer m.switch m and the adjacent integer its a

22、rrow points to.switch the direction of all integers p with pm.341.5.4鄰位對(duì)換法遞減進(jìn)位制數(shù)法啟發(fā)我們，能不能設(shè)計(jì)一種算法，下一個(gè)排列總是上一個(gè)排列某相鄰兩位對(duì)換得到的。遞減進(jìn)位制數(shù)字的換位是單向的，從右向左，逐個(gè)換位，直到最左端。鄰位對(duì)換法的換位是雙向的，通過保存數(shù)字的“方向性”來快速得到下一個(gè)排列。設(shè)定b2b3b4b5b6b7b8b9為我們要求的中介數(shù)。2的方向一定是向左。b2就是從2開始,背向2的方向所有比2小的數(shù)字的個(gè)數(shù)。知道了b2的值之后就可以依次推導(dǎo)出b3b4直到b9的值，規(guī)則如下：對(duì)于每一個(gè)大于2的數(shù)字i，如果i

23、為奇數(shù)，其方向性決定于bi-1的奇偶性，奇向右、偶向左。如果i為偶數(shù)，其方向性決定于bi-1+ bi-2的奇偶性，同樣是奇向右、偶向左。當(dāng)?shù)玫椒较蛐院?，bi的值就是背向i的方向直到排列邊界這個(gè)區(qū)間里比i小的數(shù)字的個(gè)數(shù)。如此就能得到鄰位對(duì)換法的中介數(shù)。 352的方向向左，背向2的方向中比2小的數(shù)字有1個(gè)，b2=13的方向由b2為奇可以斷定向右，背向3的方向中比3小的數(shù)字有0個(gè)，b3=04的方向由b2+b3為奇可以斷定向右，背向4的方向中比4小的數(shù)字有1個(gè)，b4=15的方向由b4為奇可以斷定向右，背向5的方向中比5小的數(shù)字有2個(gè)，b5=26的方向由b4+b5為奇可以斷定向右，背向6的方向中比6小的

24、數(shù)字有1個(gè)，b6=17的方向由b6為奇可以斷定向右，背向7的方向中比7小的數(shù)字有3個(gè)，b7=38的方向由b6+b7為偶可以斷定向左，背向8的方向中比8小的數(shù)字有7個(gè)，b8=79的方向由b8為奇可以斷定向右，背向9的方向中比9小的數(shù)字有2個(gè)，b9=2 P= 839647521 ( ) b2 b3 b4 b5 b6 b7 b8 b910121372遞減進(jìn)位制數(shù)361.5.4鄰位對(duì)換法已知(10121372)求排列。9：b8=7奇9向右 b9=2 向右第3個(gè)空，8：b6+b7=1+3=4偶8向左 b8=7 向左第8個(gè)空7：b6=1奇7向右， b7=3 向右第4個(gè)空6：b4+b5=1+2=3奇6向右，

25、b6=1,向右第2個(gè)空5：b4=1奇5向右， b5=2,向右第3個(gè)空4：b2+b3=1奇4向右, b4=1,向右第2個(gè)空3：b2=1奇3向右， b3=0,向右第1個(gè)空2：b2=1,向左第2個(gè)空38765921410121372371.5.4鄰位對(duì)換法9：b8=7奇9向右 b9=3 向右第4個(gè)空，839647521 (10121372)(10121372) +1= (10121373) 836947521836475219 (10121378)(10121378) +1= (10121400) 8364572199：b8=0偶9向左 b9=0 向左第1個(gè)空，8：b6+b7=1+4=5奇8向右 b

26、8=0 向右第1個(gè)空7：b6=1奇7向右， b7=4 向右第5個(gè)空6：b4+b5=1+2=3奇6向右，b6=1,向右第2個(gè)空。38765921438Generating PermutationsThe permutation of 1 2 3 4 41 2 31 2 3 2 31 2 31 3 21 3 2 3 21 3 24444444Each permutation other than the first one is obtained from the preceding one by switching two adjacent numbers.Move the largest number 4 between two endsWhen the end is met, the largest number 4 will be fixed for a step and the switching of the second largest number 3 makes 4 movable again.Step 0: All mobileStep 1: Choose the largest