生成排列和組合

1、第四章 生成排列和組合4.1 生成排列算法一: (生成集合1,2,n的n!個排列)基本思想是遞歸地對集合1,2,n-1的(n-1)!個排列的每一個排列, 通過把n插入到首、尾和任兩個數(shù)的中間共n個位置，產(chǎn)生集合1,2,n的n個排列，從而產(chǎn)生n´(n-1)!=n!個集合1,2,n的排列。算例： 排列n=1: 1n=2: 1 2 2 1n=3: 1 2 3 1 3 2 3 1 2 3 2 1 2 3 1 2 1 3n=4: 1 2 3 4 1 2 4 3 1 4 2 3 4 1 2 3 4 1 3 2 1 4 3 2 1 3 4 2 1 3 2 4 3 1 2 4 3 1 4 2 3 4

2、 1 2 4 3 1 2 4 3 2 1 3 4 2 1 3 2 4 1 3 2 1 4 2 3 1 4 2 3 4 1 2 4 3 1 4 2 3 1 4 2 1 3 2 4 1 3 2 1 4 3 2 1 3 4n=5:、算法結(jié)束，生成全部排列。算法二: (生成集合1,2,n的n!個排列)定義:對任一給定整數(shù)k, 其上加一個箭頭表示移動方向,或. 對于集合1,2,n的任一個排列,其中每一個整數(shù)都有一個箭頭指出其移動方向, 若整數(shù)k的箭頭指向與其相鄰但比它小的整數(shù), 稱k是活動的.算法:從開始, 當不存在活動的整數(shù)時,算法結(jié)束. (1) 求出最大的活動整數(shù)m;(2) 交換m和它箭頭所指的相鄰

3、數(shù);(3) 改變所有滿足p>m的整數(shù)p的方向.算例: (n=4)4.2 排列中的逆序定義：令i1 i2 in 是集合1,2,n的一個排列，如果 0£ k < L £n, 且ik >iL , 稱數(shù)對（ik ，iL）是排列的一個逆序。例：31524的逆序定義：令aj表示排列i1 i2 in中數(shù)j的逆序數(shù)，稱a1, a2, an為排列i1 i2 in 的逆序列。例：排列31524的逆序列逆序列的性質(zhì)：(1) 0£a1 £n-1, 0£a2 £n-2, , 0£an-1 £1, an =0。 (2) 逆序

4、列數(shù)有n!個。定理令b1, b2, bn為滿足 0£b1 £n-1, 0£b2 £n-2, , 0£bn-1 £1, bn =0的整數(shù)序列，那么存在集合1,2,n的唯一一個排列，使它的逆序列為b1, b2, bn 。證明：（構(gòu)造性證明）算法一：n:寫出整數(shù)nn-1:考慮bn-1，若 bn-1 =0，則n-1必在n的前面。 若bn-1 =1：則n-1必在n的后面。n-2:考慮bn-2，若 bn-2 =0，則n-2必在上一步得到的排列的前面。 若 bn-2 =1，則n-2必在上一步得到的排列的兩個數(shù)中間。 若 bn-2 =2，則n-2必在

5、上一步得到的排列的后面。1: 考慮b1，把1放在上一步得到的排列的第b1 個數(shù)的后面。由算法可知，從n, n-1,2,1每一步都根據(jù)b1, b2, bn 唯一地確定1,2,n在排列中的位置，兩者存在一一對應(yīng)關(guān)系。算法二：設(shè)有n個位置，標志為1,2,n1:把1放在b1+1位置上；2:把2放在第b2+1個 空 位置上；k: 把k放在第bk+1個 空 位置上；n: 把k放在余下的 空 位置上；由算法可知，根據(jù)b1, b2, bn 唯一地確定1,2,n在排列中的位置，兩者存在一一對應(yīng)關(guān)系。例1：已知1,2,8的一個排列的逆序列為：5，3，4，0，2，1，1，0，確定此排列。4.3 生成組合令集合S=x

6、n-1, xn-2, x-1, x0 ，生成S的所有2n個組合。算法：從n元組an-1an-2a1a0=000開始, 當an-1an-2a1a0=111時算法結(jié)束, 做:(1)求出使得aj=0的最小整數(shù)j; (2)用1代替aj , 并且用0代替aj-1, aj-2 , , a0 . 算法正確性證明:幾種不同的組合輸出序:(1) 字典序(2) 組合壓縮序(3) 格雷(Gray)碼序n階反射格雷(Gray)碼的遞歸定義:(1) 1階反射格雷(Gray)碼是 ;(2) 設(shè)n>1, 且n-1階反射格雷(Gray)碼已經(jīng)構(gòu)造好,首先順序列出n-1階反射格雷(Gray)碼的全部n-1元組, 并把0加

7、到全部n-1元組的開頭; 然后再反序列出n-1階反射格雷(Gray)碼的全部n-1元組, 并把1加到全部n-1元組的開頭.定義:設(shè)an-1an-2a1a0是01的n元組, 定義函數(shù)為:( an-1an-2a1a0)= an-1+an-2+a0算法: (以反射格雷(Gray)碼序生成全部 01的n元組)從n元組an-1an-2a1a0=000開始, 當an-1an-2a1a0=100時算法結(jié)束, 做:(1)計算( an-1an-2a1a0)= an-1+an-2+a0(2)若( an-1an-2a1a0)是偶數(shù), 則改變a0(0®1 或 1®0)(3) 若( an-1an-2

8、a1a0)是奇數(shù), 確定這樣的j, 使得對所有i<j, 有ai=0. 改變aj+1(0®1 或 1®0).例1：生成4階反射格雷(Gray)碼.定理算法正確性證明)上述算法產(chǎn)生n階反射格雷(Gray)碼.例2：在8階反射反射格雷(Gray)碼中,求10100110的后繼,00011101的前驅(qū).4.4 生成r組合定理4.41:令a1a2ar是1,2,n的一個r-組合, 在字典序中, 第一個r-組合是12r, 最后一個r-組合是(n-r+1) (n-r+2)n, 設(shè)a1a2ar¹(n-r+1) (n-r+2)n, 令k是滿足ak<n且使得ak+1不同于a

9、1, a2,ar 中任一數(shù)的最大整數(shù), 那么, 在字典序中, a1a2ar的直接后繼是a1a2ak-1 (ak+1)(ak+r-k+1).例1：應(yīng)用算法生成1,2,6的4-組合.定理1,2,n的r-組合a1a2ar出現(xiàn)在1,2,n的r-組合中的字典序中的位置號如下:-例2：求1,2,8的4-組合中1258的字典序位置.4.5 偏序和等價關(guān)系定義1：設(shè)X是一個集合，X上的關(guān)系定義為X ´ X上的子集（其中X ´ X是集合X的序偶的集合，即X ´ X=（a,b）½ a,bX ），令關(guān)系RÍ X ´ X，若（a,b）R ,則稱a和b有關(guān)系R

10、，記為aRb;否則稱a和b沒有關(guān)系R ,記為 ab.定義2：設(shè)R是X上的關(guān)系，R=(x,y)| x, yX 且xRy , 那么R可能具有下列性質(zhì):(1) 自反性: 若對" xX, 均有xRx;(2) 反自反性: 若對" xX, 均有xx;(3) 對稱性: 對" x,yX, 若xRy, 則必有yRx;(4) 反對稱性: 對" x,yX, x¹y, 若xRy; 則必有yx;(5) 傳遞性: 對" x,y,zX, 若xRy, yRz, 則必有xRz;定義3: 設(shè)R是X上的二元關(guān)系(1) 偏序關(guān)系:若R滿足自反性, 反對稱性和傳遞性, 則稱R

11、是X上的偏序關(guān)系. 記為” £”. 在其上定義了偏序關(guān)系的集合稱偏序集, 記為(X, £).(2) 嚴格偏序關(guān)系:若R滿足反自反性, 反對稱性和傳遞性, 則稱R是X上的嚴格偏序關(guān)系. 記為”<”.(3) 全序關(guān)系:對x,yX, 若xRy或yRx, 則稱x和y是可比的, 否則稱x和y是不可比的; 若偏序關(guān)系R使X中任兩個元素都是可比的, 則R是X上的全序關(guān)系, 記為”£”, 此時(X, £)稱全序集.(4) 等價關(guān)系:若R滿足自反性, 對稱性和傳遞性, 則稱R是X上的等價關(guān)系. 記為”或”=”.定義4: 偏序集(P, £)中, 設(shè)a,bP(

12、1) 覆蓋:若a<b, 則稱b是a的覆蓋;(2) 直接覆蓋:若a<b, 且不存在xP, 使得a<x, x<b, 則稱b是a的直接覆蓋.偏序集的幾何(哈斯圖)表示:方法:當b是a的直接覆蓋時,b與a畫一條線段, b在a的上方.例1:X=1, 2, 3, 畫出偏序集(P(A), Í)的哈斯圖.例2:X=1, 2, 3, 4, 5, 6, 7, 8, ” £”定義為整除關(guān)系, 畫出偏序集(P, £)的哈斯圖.例3:P=1, 2, 3, 4, 5, ” £”定義為實數(shù)域小于等于關(guān)系,畫出全序集(P, £)的哈斯圖.定義4:偏序集

13、(P, £)中, 若$ mP, 對" xP, 均有x £m, 則稱m是P的最大元.若nP, 對xP, 若n £x, 則必有n=x, 稱n是P的極大元.同理定義 最小元和極小元.性質(zhì):(1)偏序集未必存在最大元(最小元), 若存在必唯一.(2)偏序集一定存在極大元(極小元), 但未必唯一.設(shè)X是n個元素的有限集, 那么, 在X的全序和排列之間存在一一對應(yīng). 特別地, X上的不同全序個數(shù)是n! .定義5:令£1和£2是集合X上的兩個偏序, 對于a,bX,若有a£1b, 則必有a£2b, 那么稱偏序集(X, £2)是偏序集(X, £1)的擴展.令(X, £) 是一個有限偏序集, 則存在X上的線性序(全序) &#