排列組合的算法設(shè)計(jì)與C++實(shí)現(xiàn)

雷小園

（江西宜春學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西 宜春 336000）

1 引言

排列和組合是數(shù)學(xué)和計(jì)算機(jī)科學(xué)中的一項(xiàng)重要內(nèi)容，很多問(wèn)題（如旅行商問(wèn)題、工作分配問(wèn)題）的求解中都用到了{(lán)1,…,n}的全排列。我們知道{1,…,n}的全排列有n！中，那么該如何設(shè)計(jì)算法來(lái)得到所有的排列，并用某種語(yǔ)言編程實(shí)現(xiàn)呢？下面詳細(xì)討論了四種生成{1,…,n}的全排列的算法，還討論了一種生成{1,…,n}的字典序r-組合的算法，5種算法都用C++語(yǔ)言編程具體實(shí)現(xiàn)（由于篇幅問(wèn)題，此處沒(méi)列出C++源程序，需要源程序的本人可以提供）。

2 用換位法生成全排列

設(shè)已經(jīng)得到了{(lán)1,…,n-1}的(n-1)！個(gè)排列的表，我們可以把n插入到{1,…,n-1}的每一個(gè)排列中的n個(gè)可能的位置中去，從而得到{1,…,n}的 n(n-1)！=n！個(gè)排列的表。

我們開(kāi)始從左到右把n插入到 12…(n-1)的n個(gè)位置中去，然后每處理一個(gè){1,…,n-1}的新排列時(shí)，再調(diào)轉(zhuǎn)方向。因?yàn)檫@樣它滿足最小變化要求：僅僅需要交換相鄰的兩個(gè)元素就能得到一個(gè)新的排列。

例n=4的情況，如下：

開(kāi)始1的排列 1

從右到左將2插入1 12 21

從右到左將3插入12，再?gòu)淖蟮接覍?插入21，得到 123 132 312 321 231 213

對(duì)上面得到的6個(gè){1,2,3}的全排列，從右到左將4插入123中，再調(diào)轉(zhuǎn)方向從左到右將4插入132，再調(diào)轉(zhuǎn)方向依次插入，如下

為了得到{1,…,n}的所有排列，就先得生成并保存{1,…,n-1}的所有排列，而為了生成{1,…,n-1}的所有排列，又必須先生成{1,…,n-2}的所有排列，等等，這樣處理和編程都比較困難。

我們可以找到一種方法，不需要保留所有排列的列表，從第一個(gè)排列1,…,n開(kāi)始，每次交換相鄰的兩個(gè)數(shù)就得到一個(gè)新的排列，得到與上面相同的順序。為此，我們給每個(gè)整數(shù)k賦予一個(gè)方向，在其上面畫(huà)一個(gè)小箭頭來(lái)表示：k或k。如果一個(gè)整數(shù)k的方向指向一個(gè)相鄰的更小的整數(shù)，我們稱(chēng)這個(gè)整數(shù)是活動(dòng)的。例如，對(duì) 2 6 3 1 4 5，346是活動(dòng)的。

生成{1,…,n}的排列的算法為：

從12…n開(kāi)始，重復(fù)進(jìn)行下面3步，直到不存在活動(dòng)元素。

1)求出一個(gè)最大的活動(dòng)元素k

2)交換k和它指向的相鄰元素

3)把所有大于k的元素的方向調(diào)轉(zhuǎn)對(duì)n=3應(yīng)用該算法，如下所示：

3 用字典序法生成全排列

上面的算法得到的排列的順序不是非常自然，我們可以找到一個(gè)算法，按字典序生成{1,…,n}的所有的排列。字典序就是像在字典中單詞的排列順序一樣，所有的排列按照升序排隊(duì)。

我們先來(lái)看看從一個(gè)排列來(lái)找下字典序的一個(gè)排列。例如，對(duì){1,2,3,4,5,6}的一個(gè)排列163542，如何找它的下一個(gè)排列。為了按照字典序得到最小的變化，我們應(yīng)該盡量去換動(dòng)右面的數(shù)字。我們發(fā)現(xiàn)最后三個(gè)數(shù)字是最大的（從右到左一個(gè)比一個(gè)大），無(wú)法再做任何調(diào)整。但3小于右面的5，3542不是最大的，故可以換動(dòng)3。為了使得變化最小，應(yīng)該在3的后面找一個(gè)比3大的最小的數(shù)，這可以從右到左找到第一個(gè)比3大的數(shù)。交換這兩個(gè)數(shù)后形成164532，現(xiàn)在最后三個(gè)數(shù)依然是從大到小排列的，為使這三個(gè)數(shù)最小，可以把這三個(gè)數(shù)逆置，這樣便得到163542是下一個(gè)排列為164235。

于是，按字典序生成{1,…,n}的所有的排列的算法如下：

將12…n放置到a數(shù)組中，重復(fù)進(jìn)行以下步驟

1)從右向左找到第一個(gè)減小的元素a[m]，如果不存在這樣的元素則結(jié)束

2)再?gòu)挠蚁蜃笳业降谝粋€(gè)大于a[m]的元素a[k]

3)交換a[m]和a[k]

4)將m以后的每個(gè)數(shù)逆置，得到一個(gè)排列

4 用減治-遞歸法生成全排列

可以采用減治法，把n個(gè)數(shù)的排列，轉(zhuǎn)化為n-1個(gè)數(shù)的排列。對(duì){1,…,n}的所有的排列，我們先把1放在首位，把{2,…,n}的n-1個(gè)數(shù)進(jìn)行全排列，然后再把2放置在首位，把剩下的n-1個(gè)數(shù)進(jìn)行全排列，……，以此類(lèi)推，就得到{1,…,n}的所有的排列。為了把某個(gè)數(shù)（比如2）放到首位，可以交換這個(gè)數(shù)和第一個(gè)數(shù)，但在對(duì)剩下的數(shù)進(jìn)行全排列后，應(yīng)該再把這兩個(gè)數(shù)交換回來(lái)，以保持原有的順序不變，以便可以繼續(xù)把第一個(gè)數(shù)和另一個(gè)數(shù)（比如3）進(jìn)行交換。

5 用回溯-遞歸法生成全排列

回溯法的一個(gè)很好的例子是n皇后問(wèn)題，就是在一個(gè)n×n的棋盤(pán)上放n個(gè)皇后，使得彼此不受攻擊。全排列問(wèn)題可以看作是一個(gè)簡(jiǎn)化的n皇后問(wèn)題，{1,…,n}的n個(gè)元素看做是n個(gè)皇后，放到一個(gè)1×n的棋盤(pán)上，每種放法就對(duì)應(yīng)一個(gè)排列。

仿照n皇后問(wèn)題，得到全排列的回溯算法：先把12…n放置到a數(shù)組中，x數(shù)組用來(lái)記錄每個(gè)位置所放的是哪個(gè)元素，c數(shù)組用來(lái)記錄各個(gè)位置是否已經(jīng)放了數(shù)。對(duì)于第i個(gè)元素i，有n個(gè)可能的位置，先看第一個(gè)位置，如果可以放就放下去，同時(shí)記錄該位置已放數(shù)據(jù)。從第i+1個(gè)元素開(kāi)始將各個(gè)元素放到x數(shù)組中，當(dāng)放好第n個(gè)數(shù)后就得到一個(gè)排列。將已放下去的第i個(gè)元素拿起來(lái)，繼續(xù)看能否放到下一個(gè)位置，放好了第i個(gè)元素后繼續(xù)放置第i+1個(gè)元素。

6 組合問(wèn)題，按字典順序生成{1,2,…,n}的所有r-組合

前面均為{1,2,…,n}的全排列，下面來(lái)研究一下生成{1,2,…,n}的所有r-組合的字典排序算法。

例如，{1,2,…,8}的字典序的5-組合，第一個(gè)應(yīng)該是 12345，最后一個(gè)是 45678。對(duì)12478，我們來(lái)找它的下一個(gè)組合。和排列一樣，為了得到最小的變化，我們盡量去改動(dòng)靠右面的數(shù)字。最右面兩個(gè)數(shù)字78已是最大無(wú)法再增加，而數(shù)字4還不是這個(gè)位置的最大的數(shù)，于是可以把4加1改為5，最后兩位也跟著改為盡可能小的數(shù)67。于是得到12478的下一個(gè)組合是12567。

于是按字典序生成{1,2,…,n}的所有r-組合的算法為

從12…r開(kāi)始，重復(fù)進(jìn)行進(jìn)行以下步驟

1)從右到左找到第一個(gè)不是該位置的最大值的元素a[m]

2)將該元素加1

3)將該元素以后的元素依次遞增，得到一個(gè)組合

[1][美]Richard A.Brualdi.組合數(shù)學(xué)[M].馮舜璽譯.北京:機(jī)械工業(yè)出版社.2002:27-68.

[2][美]Richard Johnsonbaugh.離散數(shù)學(xué)(第五版)[M].石純一譯.北京:人民郵電出版社.2003:167-182.

[3][美]Anany Levitin.算法設(shè)計(jì)與分析基礎(chǔ)(第2版)[M].潘彥譯.北京:清華大學(xué)出版社.2007:136-137.