組合數(shù)學(xué)第二講

1、組合數(shù)學(xué)第二講排列的生成算法排列的生成算法 在實際工作中，需要將所有可能的排列一一羅列出在實際工作中，需要將所有可能的排列一一羅列出來加以分析，如何排列出來，需要有排列的生成算法。來加以分析，如何排列出來，需要有排列的生成算法。下面介紹幾種排列的生成算法下面介紹幾種排列的生成算法：1. 序數(shù)法序數(shù)法 2. 字典序法字典序法 3. 換位法換位法 1.序數(shù)法序數(shù)法 例例 1.11 以四個元素以四個元素1，2，3，4的排列為例，求其第的排列為例，求其第17個和第個和第 21個排列。個排列。解：四個元素解：四個元素 1，2，3，4 的第一個排列為的第一個排列為 1 2 3 4，對應(yīng)序列（，對應(yīng)序列（0

2、，0，0，0） 。） 。 和和17 116m 對應(yīng)的序列為對應(yīng)的序列為321(,)a a a，10a ，22a ，32a 。 因此，四個元素因此，四個元素 1，2，3，4 的第的第 17 個排列為個排列為 3 4 1 2。 和和21 120m 對應(yīng)的對應(yīng)的序列為序列為321(,)(3,1,0)a a a，10a ，21a ，33a 。因此，四個。因此，四個元素元素 1，2，3，4 的第的第 21 個排列為個排列為 4 1 3 2。 4 3 2 2. 字典序法字典序法 解：S1. 1max |2jjij pp S2. 1max |2ikhk pp S3. 1p和2p互換得 4321 S4. 將

3、4321 中的 321 逆轉(zhuǎn)得 4123 就是所求。 以1, 2, n的排序利用字典排序生成法，可從1, 2, n開始， 直到12 1n n 結(jié)束，即直到不存在1jjpp為止。 3. 換位法換位法 換位法看起來很直觀，但比較繁瑣。下面給出一個改進的算法換位法看起來很直觀，但比較繁瑣。下面給出一個改進的算法共參考使用：共參考使用： 對于對于1234的全排列，從的全排列，從1 2 和和2 1 開始先將開始先將3插入插入得得1 2 3 ，1 3 2，3 1 2和和2 1 3， 2 3 1，3 2 1，然后，然后將將4插入得：插入得：1 2 3 4，1 2 4 3，1 4 2 3，4 1 2 3，1

4、3 2 4，1 3 4 2，1 4 3 2 ，4 1 3 2，。，。此法推及一般，也可算是生成排列算法的一種。此法推及一般，也可算是生成排列算法的一種。允許重復(fù)的組合允許重復(fù)的組合 不相鄰的組合不相鄰的組合 組合的生成組合的生成 組合的生成比排列要簡單些。 已知12,rccc為一組不允許重復(fù)的組合，不妨假定 12rcccn，11rcn，22rcn，1,1cnr 或icnri ，1, 2,ir。而且存在12rccc，使 jcnrj ，rj 1.否則12,rccc已到最后一組，不存在后續(xù)的 組合。 組合意義的解釋組合意義的解釋 許多排列組合的公式很有實際意義，而且直觀、富許多排列組合的公式很有實際意義，而且直觀、富有啟發(fā)。后面的討論一般都指的是不允許重復(fù)的組合。有啟發(fā)。后面的討論一般都指的是不允許重復(fù)的組合。分析： （1）先從組合意義看這個公式 nr 看作是從(0, 0)點到(,)nr r點走的最短路徑數(shù)， 1nr看作是從(0, 0)點到(1,)nrr 點走的最短路徑數(shù)， 11nr看作是從(0, 0)點到(,1)nr r點走的最短路徑數(shù)。 即從(0, 0)點到(,)nr r點走的最短路徑由兩部分路徑組成，一部分是從(0, 0)點到(,1)nr r點走的最短路