一個(gè)生成組合的新算法

殷劍宏， 羅 珣

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽合肥 230009)

在許多學(xué)科中，組合在理論與應(yīng)用上都起著重要作用。n個(gè)元素集合{1，2，…，n}的組合個(gè)數(shù)為。在工程應(yīng)用中，常常需要列舉出這2n個(gè)組合，即尋找一個(gè)將集合{1，2，…，n}的2n個(gè)組合列出的系統(tǒng)過程，換句話說，就是要尋找一種生成集合{1，2，…，n}的所有組合的算法。由于n個(gè)元素集合{1，2，…，n}的組合個(gè)數(shù)很大，為了使算法在計(jì)算機(jī)上有效地運(yùn)行，算法的每一步執(zhí)行起來必須簡(jiǎn)單，算法的結(jié)果必須是一個(gè)表，該表包含集合{1，2，…，n}的每一個(gè)組合，且每一個(gè)組合只出現(xiàn)1次。

由于集合{1，2，…，n}的組合就是其子集，這樣可以利用集合{1，2，…，n}的子集和n位二進(jìn)制數(shù)之間的一一對(duì)應(yīng)關(guān)系:如果i在子集中，對(duì)應(yīng)的n位二進(jìn)制數(shù)在位置i為1;如果i不在子集中，對(duì)應(yīng)的n位二進(jìn)制數(shù)在位置i為0。這樣，如果可以列出所有的n位二進(jìn)制數(shù)，那么通過n個(gè)元素集合{1，2，…，n}的組合與n位二進(jìn)制數(shù)之間的一一對(duì)應(yīng)關(guān)系，就可以列出n個(gè)元素集合{1，2，…，n}的所有組合。

由于n位二進(jìn)制數(shù)有2n個(gè)，決定了生成所有n位二進(jìn)制數(shù)算法的時(shí)空效率均為O(2n)，即為指數(shù)復(fù)雜性。文獻(xiàn)[1-9]引入的字典序法，只能由一個(gè)n位二進(jìn)制數(shù)生成下一個(gè)n位二進(jìn)制數(shù)。本文推導(dǎo)出一個(gè)生成所有n位二進(jìn)制數(shù)的新算法，該算法具有以下優(yōu)勢(shì):理論只是初等的，且算法描述非常通俗易懂;算法的結(jié)果是一個(gè)表，該表包含每個(gè)n位二進(jìn)制數(shù)1次且僅1次;算法不必保留所有n位二進(jìn)制數(shù)的列表，就能夠簡(jiǎn)單地用后面的n位二進(jìn)制數(shù)覆蓋當(dāng)前的n位二進(jìn)制數(shù);算法是循環(huán)的;算法的每一步執(zhí)行起來非常簡(jiǎn)單，算法程序化特別容易，確保能在計(jì)算機(jī)上有效地運(yùn)行，大大地方便了工程應(yīng)用。

1 算法的歸納描述

n位二進(jìn)制數(shù)可劃分為以下2類:

(1)將0插入每一個(gè)n-1位二進(jìn)制數(shù)后，得到2n-1個(gè)不同的n位二進(jìn)制數(shù)。

(2)將1插入每一個(gè)n-1位二進(jìn)制數(shù)后，得到2n-1個(gè)不同的n位二進(jìn)制數(shù)。

由加法原理，得到2n-1+2n-1=2n個(gè)不同的n位二進(jìn)制數(shù)。

從一位二進(jìn)制數(shù)開始具體歸納描述如下:

上述歸納描述已清楚地明確對(duì)任意正整數(shù)n，如何進(jìn)行生成所有n位二進(jìn)制數(shù)的系統(tǒng)過程。同時(shí)顯示該方法恰好生成2n個(gè)不同的n位二進(jìn)制數(shù)，且每一個(gè)n位二進(jìn)制數(shù)只出現(xiàn)1次，其中:①第1個(gè)n位二進(jìn)制數(shù)為00…0，最后一個(gè)n位二進(jìn)制數(shù)為11…1;②第2n-1個(gè)n位二進(jìn)制數(shù)為11…10，第2n-1+1個(gè)n位二進(jìn)制數(shù)為00…01;③前2n-1個(gè)n位二進(jìn)制數(shù)末位上的數(shù)字均為0，后2n-1個(gè)n位二進(jìn)制數(shù)末位上的數(shù)字均為1。

定理1 按上述歸納描述，n位二進(jìn)制數(shù)a0 a1…an-2 an-1所處位置數(shù)為a0×20+a1×21+…+ an-2×2n-2+an-1×2n-1。

證明 (1)定理對(duì)于n=1，2時(shí)，顯然成立。

(2)假設(shè)定理對(duì)于n-1成立，即n-1位二進(jìn)制數(shù)a0 a1…an-2按上述歸納描述，其所處位置數(shù)為a0×20+a1×21+…+an-2×2n-2?？疾靚位二進(jìn)制數(shù)a0a1…an-2an-1，若an-1=0，則n位二進(jìn)制數(shù)a0 a1…an-2 an-1與n-1位二進(jìn)制數(shù)a0 a1…an-2的位置數(shù)相同，即n位二進(jìn)制數(shù)a0 a1…an-2an-1的位置數(shù)=a0×20+a1×21+…+an-2× 2n-2=a0×20+a1×21+…+an-2×2n-2+0× 2n-1=a0×20+a1×21+…+an-2×2n-2+an-1× 2n-1;若an-1=1，則n位二進(jìn)制數(shù)a0a1…an-2an-1的位置數(shù)=n-1位二進(jìn)制數(shù)a0 a1…an-2的位置數(shù)+2n-1=a0×20+a1×21+…+an-2×2n-2+ an-1×2n-1。

由數(shù)學(xué)歸納法，定理得證。

但是，上述歸納描述指出，要生成所有n位二進(jìn)制數(shù)，必須首先生成所有n-1位二進(jìn)制數(shù);而為了生成所有n-1位二進(jìn)制數(shù)，又必須先生成所有n-2位二進(jìn)制數(shù)等。然而，想做且僅能做的就是一次一個(gè)地生成n位二進(jìn)制數(shù)，為了生成下一個(gè)n位二進(jìn)制數(shù)而僅僅使用當(dāng)前n位二進(jìn)制數(shù)。且由于n位二進(jìn)制數(shù)的數(shù)目很大，這就要求不必保留所有的n位二進(jìn)制數(shù)列表就能夠簡(jiǎn)單地用后面的n位二進(jìn)制數(shù)覆蓋當(dāng)前的n位二進(jìn)制數(shù)。同時(shí)，要求生成n位二進(jìn)制數(shù)11…1時(shí)算法終止。

下面對(duì)上述歸納過程換種方式描述，即得到符合這些要求并按上述相同的順序生成n位二進(jìn)制數(shù)的算法。

當(dāng)n=4時(shí)的情形:

從4位二進(jìn)制數(shù)a0a1a2a3=0000開始

0000(當(dāng)前二進(jìn)制數(shù)中a0=0，改變a0)

1000(當(dāng)前二進(jìn)制數(shù)中a0=1，a1=0，改變a0，a1)

0100(當(dāng)前二進(jìn)制數(shù)中a0=0，改變a0)

1100(當(dāng)前二進(jìn)制數(shù)中a0=1，a1=1，a2=0，改變a0，a1，a2)

0010(當(dāng)前二進(jìn)制數(shù)中a0=0，改變a0)

1010(當(dāng)前二進(jìn)制數(shù)中a0=1，a1=0，改變a0，a1)

0110(當(dāng)前二進(jìn)制數(shù)中a0=0，改變a0)

1110(當(dāng)前二進(jìn)制數(shù)中a0=1，a1=1，a2=1，a3=0，改變a0，a1，a2，a3)

0001(當(dāng)前二進(jìn)制數(shù)中a0=0，改變a0)

1001(當(dāng)前二進(jìn)制數(shù)中a0=1，a1=0，改變a0，a1)

0101(當(dāng)前二進(jìn)制數(shù)中a0=0，改變a0)

1101(當(dāng)前二進(jìn)制數(shù)中a0=1，a1=1，a2=0，改變a0，a1，a2)

0011(當(dāng)前二進(jìn)制數(shù)中a0=0，改變a0)

1011(當(dāng)前二進(jìn)制數(shù)中a0=1，a1=0，改變a0，a1)

0111(當(dāng)前二進(jìn)制數(shù)中a0=0，改變a0)

1111(當(dāng)前二進(jìn)制數(shù)中a0=a1=a2=a3=1，算法終止)

具體算法描述如下:

從n位二進(jìn)制數(shù)a0a1…an-2an-1=00…00開始，當(dāng)a0 a1…an-2 an-1≠11…11時(shí):①?gòu)淖笙蛴覓呙枵易钚〉恼麛?shù)j使得aj=0;②改變a0，a1，…，aj的值(即a0，a1，…，aj-1的值均由1變?yōu)?; aj的值由0變?yōu)?)。

注意:對(duì)于最后一個(gè) n位二進(jìn)制數(shù)a0 a1…an-2 an-1=11…11，由于a0=a1=…=an-1=1，從而改變a0，a1，…，an-1的值得到其直接后繼n位二進(jìn)制數(shù)00…00，因此算法是循環(huán)的。

定理2 上面描述的算法，對(duì)每個(gè)正整數(shù)n產(chǎn)生2n個(gè)不同的n位二進(jìn)制數(shù)。

證明 (1)算法用于n=1，2時(shí)，定理顯然成立。

(2)假設(shè)算法用于n-1時(shí)，產(chǎn)生2n-1個(gè)不同的n-1位二進(jìn)制數(shù)。

設(shè)當(dāng)前n位二進(jìn)制數(shù)為a0 a1…aj-1 aj a j+1…an-2 an-1，其中a0=a1=…=aj-1=1，aj=0。

若j=n-1，即a0 a1…an-2 an-1=11…10，則a0a1…an-2an-1是第2n-1個(gè)n位二進(jìn)制數(shù)，改變a0，a1，…，an-1的值，顯然得到第2n-1+1個(gè)n位二進(jìn)制數(shù)為00…01。

若j≠n-1，則a0a1…aj-1ajaj+1…an-2an-1一定不是第2n-1個(gè)n位二進(jìn)制數(shù)，換句話說，a0 a1…aj-1 aj a j+1…an-2 an-1的直接后繼n位二進(jìn)制數(shù)末位上的數(shù)字仍為an-1。又a0a1…aj-1ajaj+1…an-2是n-1位二進(jìn)制數(shù)，改變a0，a1，…，aj-1，aj的值即得其直接后繼n-1位二進(jìn)制數(shù)00…01 aj+1…an-2。因此，n位二進(jìn)制數(shù)為a0 a1…aj-1 aj aj+1…an-2 an-1的直接后繼n位二進(jìn)制數(shù)為00…01 aj+1…an-2an-1。由數(shù)學(xué)歸納法，定理得證。

2 舉 例

生成6位二進(jìn)制數(shù)，結(jié)果用4列顯示，其中第1列為前16個(gè)6位二進(jìn)制數(shù)，第2列為順數(shù)第2個(gè)16個(gè)6位二進(jìn)制數(shù)，…，最后一列為最后16個(gè)6位二進(jìn)制數(shù)。

000000 000010 000001 000011

100000 100010 100001 100011

010000 010010 010001 010011

110000 110010 110001 110011

001000 001010 001001 001011

101000 101010 101001 101011

011000 011010 011001 011011

111000 111010 111001 111011

000100 000110 000101 000111

100100 100110 100101 100111

010100 010110 010101 010111

110100 110110 110101 110111

001100 001110 001101 001111

101100 101110 101101 101111

011100 011110 011101 011111

111100 111110 111101 111111

3 結(jié)束語(yǔ)

本文首先以加法原理為理論，得到一個(gè)將所有2n個(gè)n位二進(jìn)制數(shù)列出的系統(tǒng)過程，深刻分析了該系統(tǒng)過程的內(nèi)在本質(zhì)，進(jìn)而得到一個(gè)易于計(jì)算機(jī)處理的歸納描述，且只用到數(shù)學(xué)歸納法的思想，并進(jìn)行了理論上的證明。本文給出的算法，其理論只是初等的，算法描述非常通俗易懂，且是循環(huán)的;同時(shí)算法的結(jié)果是一個(gè)表，不必保留所有n位二進(jìn)制數(shù)的列表，能夠簡(jiǎn)單地用后面的n位二進(jìn)制數(shù)覆蓋當(dāng)前的n位二進(jìn)制數(shù)，且算法的每一步執(zhí)行起來非常簡(jiǎn)單，因而易于計(jì)算機(jī)處理，大大方便了工程應(yīng)用。

[1] 陳景潤(rùn).組合數(shù)學(xué)簡(jiǎn)介[M].天津:天津科學(xué)技術(shù)出版社，1988:42-55.

[2] Reingold E M，Nievergelt J，Deo N.Combinatorial algorithm s:theory and practice[M].Englew ood Cliffs，NJ: Prentice H all，1977:111-120.

[3] Trotter H F.A lgorithm 115[J].Communications of the Association for Compu ting Machinery，1962，5:434-435.

[4] Even S.A lgorithm ic combinatorics[M].New York:Macm illan，1973:67-79.

[5] Brualdi R A.Introductory combinatorics[M].北京:機(jī)械工業(yè)出版社，2003:81-93.

[6] Brualdi R A.組合數(shù)學(xué)[M].馮舜璽，羅 平，裴偉東，譯.北京:機(jī)械工業(yè)出版社，2003:50-57.

[7] Roberts F S，Tesm an B.應(yīng)用組合數(shù)學(xué)[M].馮 速，譯.北京:機(jī)械工業(yè)出版社，2007:60-61.

[8] 殷劍宏.組合數(shù)學(xué)[M].北京:機(jī)械工業(yè)出版社，2006: 12-18.

[9] 殷劍宏，汪榮貴，薛 峰.生成圖的全部極大獨(dú)立集的一般方法[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2008，31(3): 479-483.