呵呵:)全组合是本人根据全排列的说法创造的,其表达的内容是:将2Cn到(n-1)Cn对应的字符串序列依次输出(当然了,会去掉组合数值相同的组合排列,也就是只需要计算2~(n-1)/2)),这样能够满足特定部门的需求。
大家都知道计算排列组合的普通算法的时间复杂度是O(N*N)当N达到一定程度的时候普通的计算机是不能够承受的,所以在计算这种对应字符串全组合需要一种高效的组合算法,使普通的机子能够承受。对字符串进行不同m值的组合,首先我们想到的是用一个整型数组中的每一位来对应字符串中的每一个字符,这样对数组中的元素的移动形成的不同排列,将其抽取出来对应的字符就是不同的字符组合,进行一定次数控制的循环就可以形成全组合字符序列的排列了。其具体算法如下:
组合算法
本程序的思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标
代表的数被选中,为0则没选中。
首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。
然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为
“01”组合,同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得
到了最后一个组合。
例如求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
在具体的代码编写过程中,会遇到很多的问题,例如0、1转换后的数组与1元素归前之后的数组如何协调进行下次0、1转换的先后次序,等等的这些问题,需要我们一个一个解决。下面我将关键的代码贴出来方便大家:
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开始,到n-2Cn结束,每一种情况下的排列都要在下面移动一次,这里还要考虑组合
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 // 用于判断是否之前移动过这样的序列,移动过则不进行移动了
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 // 这里的循环次数是根据不同的组合来的,与前面的z值有关。
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 // 这里会有movedArray swap之后和以前一样,无法输出,
50 // 又和tempArray不一样,在这里进入死循环的情况
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 }
本文依据《创作共用约定》之“署名-禁止派生-非商业用途”方式发布,即你可以免费拷贝、分发、呈现和表演当前作品,但是必须基于以下条款:
对于任何二次使用或分发,你必须让其他人明确当前作品的授权条款。
在得到作者的明确允许下,这里的某些条款可以放弃。