組合數(shù)學(xué)7

1、1,第四章 生成排列和組合 4.3 生成組合,令n個元素的集合 S={xn-1,xn-2,…,x1,x0}。我們尋找一種生成S的所有組合（或者說子集）的算法，算法的結(jié)果應(yīng)該僅僅是S的組合。 由前面的知識，我們可以分別從S取出0,1,2,..n個元素來構(gòu)造子集合的個數(shù)共計有：,2,給定S的一個組合A, 當(dāng)?A?= n 時， A= S ; 當(dāng) ?A?＜n時，組合A中不包含S的所有元素，則S的

2、每一個元素xi或者屬于A或者不屬于A，如果用1表示是屬于A，用0表示不屬于A，那么就能用2n個字符 組合成長度為n的1和0的n元組： (an-1, an-2,…, a1, a0) = an-1 an-2…, a1 a0 (ai =0,1 ) 來區(qū)分集合S的2n個組合(子集)。對于每個i=0,1,….n-1, 令n元組的第 ai 項對應(yīng)于元素xi 。,3,例: 當(dāng) n = 3 時， 23 =

3、8 個組合以及它們對應(yīng)的3 元組如下：,可以看出：組合中有哪個元素，在序列相應(yīng)位置上就有個 1 ；第一列相當(dāng)于集合{ x2, x1, x0 }的冪集。,,4,例:令 S={x6,x5,x4,x3,x2,x1,x0}. S的組合 {x5,x4,x2,x0} 是 個中的一個，對應(yīng)的7元組是:0110101;同樣7元組1010001對應(yīng)的組合是：{x6, x4, x0} 由于n個元素

4、的組合可以用0和1的n元組確定，為了生成n個元素的集合的所有組合，只要能夠以表的形式寫出0和1的2n個n元組的系統(tǒng)的過程就足夠了?，F(xiàn)在每一個n元組都可以看成是基礎(chǔ)為2的一個數(shù)（二進(jìn)制記數(shù)）。,5,例：10011是整數(shù)19的二進(jìn)制數(shù)，因為： 19 = 1×24 + 0×23+0×22+1× 21 + 1×20 一般地，給定一個從0到2n-1的整數(shù)m , 則數(shù)m可以

5、由如下形式表示： m = an-1 2n-1 + an-1 2n-2 +…+ a1 21 + a0 20 其中每個ai 是0和1，反之亦然。 因此， 0和1的n元組與整數(shù)0,1,2,…. 2n-1之間存在一一對應(yīng)。,6,于是生成 S＝ {xn-1,xn-2,…,x1,x0}的2n個組合的問 題就轉(zhuǎn)化成生成2n個n位二進(jìn)制數(shù)的問題。 現(xiàn)在就變的簡單了：以

6、由小到大的順序?qū)懗鰪?到2n-1的數(shù)，但要轉(zhuǎn)化成二進(jìn)制形式，使用基為2的運算每次加1遞增。例:令n = 7。數(shù)29在0和27-1之間并且可以表示成 29 = 0×26 +0×25 +1×24+1×23+1×22 +0× 21 + 1×20,7,因此，29就有一個由0011101給出的7位數(shù)字

7、的二進(jìn)制數(shù)表示并且對應(yīng)集合： S＝ {x6, x5, x4 , x3, x2, x1, x0}的一個組合： {x4 , x3, x2, x0}；同樣可以求出整數(shù)29在0和25-1之間的二進(jìn)制表示和對應(yīng)的5元組如下： 29 = 0×25 +1×24+1×23+1×22 +0× 21 + 1×20與5位

8、基2數(shù) 11101 和組合{x4 , x3, x2, x0}對應(yīng)。,8,生成S={xn-1,xn-2,…,x1,x0}的2n個組合，或者說生 成0和1的2n個n元組，只要用二進(jìn)制形式， 使用基為2的運算每次加1，再按由小到大順序?qū)懗鰪?到2n – 1的數(shù)，使他們一一對應(yīng)。 組合序列 ? 基為2的n元組 ? 0到2n – 1的整數(shù)例：生成0和1的4元組；解：4元組共有 24=16個數(shù)，

9、 如下表：,9,,,10,例：緊接集合S＝ {x6, x5, x4 , x3, x2, x1, x0}的一個 組合 {x6, x4 , x2, x1, x0}后面的組合是什么？解：組合 {x6, x4 , x2, x1, x0}對應(yīng)的二進(jìn)制數(shù)是： 1010111。用基為2的運算，下一個組合應(yīng)該對應(yīng)： 1010111 + 1

10、 1011000此二進(jìn)制數(shù)對應(yīng)的組合是： {x6, x4 , x3},,11,例：集合S＝ {x6, x5, x4 , x3, x2, x1, x0}的哪個組合 是表的第108組合？它前后的組合是什么？解：將108寫成基為2的數(shù)： 108 = 1×26 +1×25 +0×24+1×23+1×22

11、 +0× 21 + 0×20對應(yīng)7位二進(jìn)制數(shù) 1101100；組合{x6, x5, x3, x2,}前一個是：1101011；組合{x6, x5, x3, x1, x0}后一個是：1101101；組合{x6, x5, x3, x2, x0},12,生成{xn-1,xn-2,…,x1,x0}的組合的基2算法： 1. 輸入大于等于1的整數(shù)n；

12、 2. 構(gòu)造空組合對應(yīng)的二進(jìn)制數(shù)an-1 an-2… a1 a0=00…00； 并輸出； 3. 當(dāng) an-1 an-2… a1 a0≠ 11…11時，做： i）在n-1到0之間求出使得aj＝0的最小整數(shù)j； ⅱ）用1代替aj并用0代替aj-1 , aj-2, … , a1, a0中的每一個； ⅲ） 輸出當(dāng)前求出的新的組合an-1 an-2… a1 a0。,13,例. 輸入大于

13、等于1的整數(shù)n； 初始時組合對應(yīng)的二進(jìn)制數(shù)： an-1 an-2… a1 a0=00…00； 其中使得aj＝0的最小整數(shù)j 是0. (即倒數(shù)第一位的a0) 用1代替a0并用0代替其他aj-1 , aj-2, … , a0,(實際上沒有比a0更前面的數(shù)了)得到第一個二進(jìn)制序列000...001。,14,第二次：對于序列；an-1 an-2… a1 a0=00…

14、01； 其中使得aj＝0的最小整數(shù)j 是1. (即倒數(shù)第二位的a1) 用1代替a1并用0代替其他a1 前面的數(shù)a0, 得到第一個二進(jìn)制序列000...010. 如此下去就有：000...011. 再下去就有：000...100；100...101；....... .........111...1111；,15,利用字典序來討論

15、給出兩個不同的單詞，為了確定在字典中的順序，我們將比較單詞的字母。有兩種可能性： 1.兩個單詞長度不同，較短單詞的每個字母與較長單詞的相應(yīng)字母相同。 2.兩個單詞長度不同或相同，單詞的某些位置的字母不同。 如果1成立，則較短單詞排在較長單詞之前。,16,（例如，在字典中“dog”排在“doghouse”之前）。 如果2成立，我們把字母不同的最左位置稱為P

16、位置。單詞的順序由P位置的字母順序決定。（例如，在字典中“gladiator”排在“gladiolus”之前。在字母不同的最左位置，“gladiator”中為“a”，而“gladiolus”中為“o”，字母表“a”排在“o”之前。二十六個字母的順序是固定的）稱按照上述兩規(guī)則排列的字符串遵守了字典序。,17,字典序是通過用任意一個已定義順序的有序 符號集合代替字母表來構(gòu)造普通的字典順序。我們將討論整數(shù)字符串問題，通過基2

17、算法生成的0和1的n元組的順序叫做n元組的字典序。在字典序下，假設(shè)表中有兩個n元組an-1 an-2… a1 a0和bn-1 bn-2… b1 b0,從左邊開始，如果出現(xiàn)第一個位置的字符不同，例如aj=0 而bj =1，那么： an-1 an-2… a1 a0序列就在bn-1 bn-2… b1 b0的前面(這里,18,說明兩個序列在第j個位置以前的字符都相同） 也就是說前一個序列給出的基為2的數(shù)小于后一個序列給出的基為

18、2的數(shù)。與字典序中二十六個字母的順序一樣，我們把基為2的數(shù)中 “0”和“1”看作字母，并且規(guī)定“0”在“1”的前面，這樣n元組就可以看成長度為n的“單詞”，字典序就是這些單詞出現(xiàn)在字典中的順序。 將n元組減少部分元素后夠成的序列的順序,19,關(guān)系如下： 把n元組看成集合{xn-1,xn-2,…,x1,x0}的組合，那么對于每一個滿足n－1＞j 的 j ,{xj, …,x1,x0}的所有的組合先于至少

19、含有xn-1,xn-2,…,xj+1中一個元素的那些組合。因為{xj, …,x1,x0}的元素都小于xn-1,xn-2,…,xj+1中的任一個。由于這個原因，有時0和1的n元組若看成集合{xn-1,xn-2,…,x1,x0}的組合的順序也叫做組合的壓縮序。,20,我們用壓縮序?qū)?dāng)前那些元素的所有組合 列在引進(jìn)一個新元素后的組合前面。 例如：集合{x3 = 4, x2 = 3,x1 = 2, x0 =1}的諸壓縮序

20、在下面列出，前兩列元素的組合是列在“4”元素之前的，可以看出，列出{1，2，3}的組合后，將第四個元素直接添加，就能得到余下的組合；將第二列和第五列并在一起就得到。集合{4, 3, 2, 1}的全部16個組合。,21,注意，不含4的組合在包含4的組合前面，同理，不含3的組合在包含3的組合前面………,22,組合的壓縮序中，相鄰的組合可能差別很大 例如： 集合{x6,x5,…,x1,x0}的一個組合： A= {x6,

21、x4, x3} (對應(yīng)7元組1011000)與下一位置的組合B = {x6, x4, x2, x1, x0}(對應(yīng)7元組1010111)有多處不同，于是我們考慮：能否以不同的順序生成n個元素的組合與它前后的組合差距盡可能的??？即前后組合僅僅通過增加或者刪除一個元素而得到。簡單說一進(jìn)一出就得到，這種方案可降低生成所有組合時候的誤差。,23,例：令S={xn-1,xn-2,…,x1,x0}，分析S的組合以及 n= 1，2，

22、3時對應(yīng)的n元組的情況。解：,觀察發(fā)現(xiàn)，從一個組合到另一個組合的轉(zhuǎn)換就是加入一個新元素同時減少一個舊元素，,,,,24,而不是同時都進(jìn)行;用0和1的n元組的術(shù)語來說, 就 是把0變成1或者把1變成0，而不能同時都變。 我們可以進(jìn)一步利用幾何表示來說明生成組合的方法。把0和1的n元組當(dāng)成n維空間中一個點的坐標(biāo)。對于n=1，這種表示就是一條直線(數(shù)軸)上的點；對于n=2，這種表示就是平面上的點； 對于n=3，

23、這種表示就是空間中的點。 例:令n=1; 0和1的1元組對應(yīng)單位線段的兩個端點,25,令n=2; 0和1的2元組對應(yīng)單位正方形的四個端點 10 11 0 1

24、 00 01令n=3; 0和1的3元組對應(yīng)單位正方體的八個端點 110 111 010 011

25、 100 101 000 001,,,,,,,,,,,,,,,26,注意，通過上面三個例子發(fā)現(xiàn)有這樣的特點： 每兩個角點間，當(dāng)它們的坐標(biāo)只有一處不同時，恰好在一條公共邊上。 將這個結(jié)論推廣到單位n-方體，它有2n

26、個角，它們的每個坐標(biāo)都是0和1的2n個n元組，當(dāng)兩個角點的坐標(biāo)只有一處不同時，恰好有一條邊連接這兩個角點，生成0和1的n元組的算法對應(yīng)著沿單位n-方體的邊訪問每個角點恰好一次的路徑，,27,如同圖論中的“歐拉路”和 “歐拉回路” ； 其中每個n元組具有以下性質(zhì)：n元組的后繼僅僅有一處與該n元組不同。這樣，任意一條路徑稱為n階Gray碼(葛萊碼，二進(jìn)制循環(huán)碼)。如果再穿過一條邊從路徑的終點回到起點，那么Gray碼叫做是循

27、環(huán)的。 例 從單位1-方體開始，始于0終于1的Gray碼是： 0 1,,28,通過拷貝兩個1-方體并且連接對應(yīng)的角點就可 以得到一個單位2-方體，具體方法是：把0附加在一個拷貝的兩個坐標(biāo)前，把1附加在另一個單位1-方體的兩個坐標(biāo)前： 10 11 首先沿著1-方體的一個拷貝 的Gray碼行進(jìn)，

28、穿行到另一 個1-方體，再沿這個1-方體的 00 01 Gray碼以相反的順序行進(jìn), 這樣得到的4個Gray,,,,,拷貝,反射Gray碼順序,,Gray碼順序,,29,碼順序分別為：00，01，11，10； 用同樣方法可以構(gòu)造單位3-方體，以及單位n-方體。我們就單位3-方體的Gray碼給予說明； 將2階Gray碼 00，01，11，10拷貝一份得：

29、 00，01，11，10 ； 00，01，11，10分別在前一份數(shù)碼前加0，在后一份數(shù)碼前加1。 000，001，011，010 ； 100，101，111，110得到的3階Gray碼的順序與基2算法的順序不同。,30,由于穿行到另一個拷貝后是沿這個拷貝的Gray碼 相反順序行進(jìn)，我們稱用這種方式夠建的Gray碼為反射Gray碼。可以對n≥1用歸納法構(gòu)建n階Gray碼。 例：構(gòu)建3階Gray碼。由2

30、階Gray碼拷貝出：,,,,,,,,,,,,,,,,,,10,101,111,001,000,00,01,11,010,011,110,100,31,其中紫色的字符是 拷貝后加上去的， 反射Gray碼確定了箭頭的方向。,,,,,,,,,,,,,,,,,,10,101,111,001,000,00,01,11,010,011,110,,,,,,,,,,,100,,32,例 :4階反射Gray碼由3階反射Gray碼加0或1得

31、到;黃框是1階,藍(lán)框是2階,黑框是3階反射Gray碼， 右邊的是拷貝，基2碼表示如下右表：,,,,,,,,33,n階反射Gray碼的一般歸納定義 i）1階反射Gray碼是 ⅱ）設(shè)n＞1 且n-1階反射Gray碼已經(jīng)構(gòu)造好。首先用n-1階反射Gray碼給出的順序列出0和1的(n-1)-元組，把0添加到每個(n-1)元組的開頭，然后以n-1階反射Gray碼給出順序(反向n-1階的順序)的相

32、反順序再列出(n-1)元組，并把1添加到每個(n-1)元組的開始處。,01,34,由上歸納定義可知， n階反射Gray碼是以 n-元組00…..00開始并以n-元組100…00結(jié)束。由于00…..00與100…00只有一處不同，因此該碼是循環(huán)的。 構(gòu)造n階反射Gray碼要先構(gòu)造n-1階反射Gray碼，例如要7階反射Gray碼，就必須先構(gòu)造1,2,3,…6 階反射Gray碼。這需要一個逐次性法則。下面我們給

33、出算法；,35,以反射Gray碼的順序生成0和1的n 元組的算法 我們用σ=σ(an-1 an-2… a1 a0)= an-1 +… + a0表示0和1的n 元組an-1 an-2… a1 a0中1的個數(shù)。 1. 生成組合an-1 an-2… a1 a0 =00…00；并輸出； 2. 當(dāng)an-1 an-2… a1 a0 ≠ 10…00時，做：ⅰ) 計算σ ＝ an-1 ＋an-2＋…＋ a1 ＋a0ⅱ) 當(dāng)σ

34、偶數(shù)，則改變a0(從0變到1或從1變到0)； iii)否則,從右向左找第一個aj=1; 按ⅱ)改變aj＋1；,36,定理4.3.1上面描述的生成0和1的n-元組的算法 對每個正整數(shù)n產(chǎn)生n階反射Gray碼。證明：可用對n的歸納來證明（省略）。 通過觀察n=3,4的反射Gray碼相鄰的碼之間都有這些特點；,37,該定理正好給出了相鄰的反射Gray碼之間的關(guān) 系，我們可以利用它求反射Gra

35、y碼的后繼。例：在8階反射Gray碼中，確定10100110， 01010100 ，和00011111的后繼8-元組。解：由于σ(10100110) = 4（ 8-元組中1的個數(shù)） 是偶數(shù)，由算法ⅱ) 改變末尾的a0(從0變到1或從1變到0)；它的后繼是10100111，,38,由于σ(01010100) = 3 是奇數(shù)，由算法iii) 確定j, 從右向左找第一個aj=1; 改變a

36、j＋1； 原式中 a2=1而a1 = a0= 0，故選擇j = 2，改變aj＋1 =a3后得到它的后繼： 01011100； 由于σ(00011111) = 5 是奇數(shù)，由算法iii) a0 = 1，故選擇j = 1，改變aj＋1 = a2后得到它的后繼： 00011101 ；,39,總 結(jié),本次課我們學(xué)習(xí)了生成組合的兩個算法，要求掌握基2算法和反射Gray碼算法以及這兩個算法的應(yīng)用等知識。,40,本次授

37、課到此結(jié)束,作業(yè)如下: P73 11, 12, 15， 23,11.令S={x7,x6,…,x1,x0}。確定對應(yīng)S的下列組 合的0和1的8-元組.(1) {x5,x4, x3}; (2) {x7,x5, x3,x1}; (3){x6},41,12.令S={x7,x6,…,x1,x0}。確定S對應(yīng)下列8-元組的組合.(1) 000110011; (2) 01010101; (3)0

38、000111115.對于{x7,x6,…,x1,x0}的下列每一組合，通過使用基為2的生成算法確定其直接后繼組合.(1) {x4,x1, x0}; (2) {x7,x5, x3}; (3){x7,x5, x4,x3,x2, x1, x0}； (3) {x0};,42,23.確定下列9階反射Gray碼中9-元組的直接后繼。（1）010100110； （2）110001100；