??? 呵呵:)全組合是本人根據(jù)全排列的說(shuō)法創(chuàng)造的,其表達(dá)的內(nèi)容是:將2Cn到(n-1)Cn對(duì)應(yīng)的字符串序列依次輸出(當(dāng)然了,會(huì)去掉組合數(shù)值相同的組合排列,也就是只需要計(jì)算2~(n-1)/2)),這樣能夠滿足特定部門的需求。
??? 大家都知道計(jì)算排列組合的普通算法的時(shí)間復(fù)雜度是O(N*N)當(dāng)N達(dá)到一定程度的時(shí)候普通的計(jì)算機(jī)是不能夠承受的,所以在計(jì)算這種對(duì)應(yīng)字符串全組合需要一種高效的組合算法,使普通的機(jī)子能夠承受。對(duì)字符串進(jìn)行不同m值的組合,首先我們想到的是用一個(gè)整型數(shù)組中的每一位來(lái)對(duì)應(yīng)字符串中的每一個(gè)字符,這樣對(duì)數(shù)組中的元素的移動(dòng)形成的不同排列,將其抽取出來(lái)對(duì)應(yīng)的字符就是不同的字符組合,進(jìn)行一定次數(shù)控制的循環(huán)就可以形成全組合字符序列的排列了。其具體算法如下:
組合算法 ?
? 本程序的思路是開(kāi)一個(gè)數(shù)組,其下標(biāo)表示1到m個(gè)數(shù),數(shù)組元素的值為1表示其下標(biāo) ?
? 代表的數(shù)被選中,為0則沒(méi)選中。 ? ?
? 首先初始化,將數(shù)組前n個(gè)元素置1,表示第一個(gè)組合為前n個(gè)數(shù)。 ? ?
? 然后從左到右掃描數(shù)組元素值的“10”組合,找到第一個(gè)“10”組合后將其變?yōu)??
? “01”組合,同時(shí)將其左邊的所有“1”全部移動(dòng)到數(shù)組的最左端。 ? ?
? 當(dāng)?shù)谝粋€(gè)“1”移動(dòng)到數(shù)組的m-n的位置,即n個(gè)“1”全部移動(dòng)到最右端時(shí),就得 ?
? 到了最后一個(gè)組合。 ? ?
? 例如求5中選3的組合: ? ?
? 1 ? 1 ? 1 ? 0 ? 0 ? //1,2,3 ? ?
? 1 ? 1 ? 0 ? 1 ? 0 ? //1,2,4 ? ?
? 1 ? 0 ? 1 ? 1 ? 0 ? //1,3,4 ? ?
? 0 ? 1 ? 1 ? 1 ? 0 ? //2,3,4 ? ?
? 1 ? 1 ? 0 ? 0 ? 1 ? //1,2,5 ? ?
? 1 ? 0 ? 1 ? 0 ? 1 ? //1,3,5 ? ?
? 0 ? 1 ? 1 ? 0 ? 1 ? //2,3,5 ? ?
? 1 ? 0 ? 0 ? 1 ? 1 ? //1,4,5 ? ?
? 0 ? 1 ? 0 ? 1 ? 1 ? //2,4,5 ? ?
? 0 ? 0 ? 1 ? 1 ? 1 ? //3,4,5
在具體的代碼編寫過(guò)程中,會(huì)遇到很多的問(wèn)題,例如0、1轉(zhuǎn)換后的數(shù)組與1元素歸前之后的數(shù)組如何協(xié)調(diào)進(jìn)行下次0、1轉(zhuǎn)換的先后次序,等等的這些問(wèn)題,需要我們一個(gè)一個(gè)解決。下面我將關(guān)鍵的代碼貼出來(lái)方便大家:
?1?public?StringBuffer?outputRankedPrescription()?throws?IOException?{
?2?????????String?serialString?=?null;
?3?
?4?????????StringBuffer?stringBuffer?=?new?StringBuffer();
?5?
?6?????????this.inputPrescription();
?7?????????String[]?prescriptionArray?=?this.splitPrescription2Array();
?8?
?9?????????int[]?intArray?=?this.generateIntArray(prescriptionArray);
10?????????//?生成初始序列
11?????????intArray[0]?=?1;
12?????????intArray[1]?=?1;
13?????????this.printArrayElement(prescriptionArray,?intArray);
14?
15?????????intArray?=?resetArrayElement(intArray);
16?????????//?從2Cn開(kāi)始,到n-2Cn結(jié)束,每一種情況下的排列都要在下面移動(dòng)一次,這里還要考慮組合
17?????????//?有相同的情況,這樣就不用多輸出了
18?????????for?(int?z?=?1;?z?<?intArray.length?-?1;?z++)?{
19?????????????if?((z?-?0)?==?(intArray.length?-?z?-?1))
20?????????????????continue;
21?????????????HashMap?posHashMap?=?new?HashMap();
22?
23?????????????int[]?tempArray?=?null;
24?????????????intArray[z]?=?1;
25?????????????if?(z?!=?1)?{
26?????????????????this.printArrayElement(prescriptionArray,?intArray);
27?????????????}
28?????????????this.registerPosition(intArray,?posHashMap);
29?????????????tempArray?=?this.swapArrayElement(intArray);
30?????????????serialString?=?this.getPosSerial(tempArray);
31?????????????//?用于判斷是否之前移動(dòng)過(guò)這樣的序列,移動(dòng)過(guò)則不進(jìn)行移動(dòng)了
32?????????????if?(!posHashMap.containsKey(serialString))?{
33?????????????????printArrayElement(prescriptionArray,?tempArray);
34?????????????????this.registerPosition(tempArray,?posHashMap);
35?????????????????tempArray?=?resetArrayElement(tempArray);
36?????????????}
37?????????????//?只需要組合2到n-1的這種情況
38?????????????int[]?movedArray?=?null;
39?????????????boolean?isEqual?=?true;
40?????????????boolean?isTemp?=?false;
41?????????????boolean?isAlreadyHad?=?false;
42?????????????//?這里的循環(huán)次數(shù)是根據(jù)不同的組合來(lái)的,與前面的z值有關(guān)。
43?????????????int?loopSize?=?Combination.calculateCombinationValue(
44?????????????????????intArray.length,?z?+?1);
45?????????????while?(posHashMap.size()?!=?loopSize)?{
46?????????????????if?(movedArray?!=?null)
47?????????????????????isEqual?=?this.isArrayMatch(tempArray,?isEqual,?movedArray);
48?????????????????if?(isEqual?==?false?&&?!isAlreadyHad)?{
49?????????????????????//?這里會(huì)有movedArray?swap之后和以前一樣,無(wú)法輸出,
50?????????????????????//?又和tempArray不一樣,在這里進(jìn)入死循環(huán)的情況
51?????????????????????if?(isTemp?==?true)?{
52?????????????????????????movedArray?=?this.swapArrayElement(movedArray);
53?????????????????????????serialString?=?this.getPosSerial(movedArray);
54?????????????????????}?else?{
55?????????????????????????tempArray?=?this.swapArrayElement(movedArray);
56?????????????????????????serialString?=?this.getPosSerial(tempArray);
57?????????????????????}
58?
59?????????????????????if?(posHashMap.containsKey(serialString))?{
60?????????????????????????isAlreadyHad?=?true;
61?????????????????????}
62?????????????????????if?(!posHashMap.containsKey(serialString)?&&?isTemp)?{
63?????????????????????????//?輸出
64?????????????????????????movedArray?=?manageArrayOutput(posHashMap,
65?????????????????????????????????prescriptionArray,?movedArray,?isEqual);
66?????????????????????}?else?if((!posHashMap.containsKey(serialString)?&&?!isTemp)){
67?????????????????????????movedArray?=?manageArrayOutput(posHashMap,
68?????????????????????????????????prescriptionArray,?tempArray,?isEqual);
69?????????????????????}
70?????????????????}?else?{
71?????????????????????tempArray?=?resetArrayElement(tempArray);
72?????????????????????tempArray?=?this.swapArrayElement(tempArray);
73?????????????????????serialString?=?this.getPosSerial(tempArray);
74?????????????????????if?(!posHashMap.containsKey(serialString))?{
75?????????????????????????//?輸出
76?
77?????????????????????????movedArray?=?manageArrayOutput(posHashMap,
78?????????????????????????????????prescriptionArray,?tempArray,?isEqual);
79?????????????????????}?else?{
80?????????????????????????isTemp?=?true;
81?????????????????????}
82?????????????????????isAlreadyHad?=?false;
83?????????????????}
84?????????????}
85?????????}
86?????????return?stringBuffer;
87?????}

本文依據(jù)《創(chuàng)作共用約定》之“署名-禁止派生-非商業(yè)用途”方式發(fā)布,即你可以免費(fèi)拷貝、分發(fā)、呈現(xiàn)和表演當(dāng)前作品,但是必須基于以下條款:

  • 署名:你必須明確標(biāo)明作者的名字。

  • 非商業(yè)用途:你不可將當(dāng)前作品用于商業(yè)目的。

  • 禁止派生:你不可更改、轉(zhuǎn)變或者基于此作品重新構(gòu)造為新作品。

對(duì)于任何二次使用或分發(fā),你必須讓其他人明確當(dāng)前作品的授權(quán)條款。

在得到作者的明確允許下,這里的某些條款可以放棄。