In my lastest project on Database course, I try to find an optimal joining plan to excuate the sql query. I choose Dynamic Programming to implement my programming. To implement this algorithm, I need to design a class to find all the combinations by selecting m random numbers from n numbers. After searching for methods from google and baidu, I write a class to implement my algorithm successfully. Now I show my codes for sharing. Wish them will help others.
1
package qp.optimizer;
2
3import java.io.*;
4
5import java.util.BitSet;
6import java.util.Vector;
7
8import qp.utils.RandNumb;
9
10
public class CombSubset 
{
11
int[] init;
12 int[][] end;
13 int[][] left;
14 int n;
15 int m;
16 int numset;
17 String[] relstr;
18 String[] leftstr;
19 int count;
20 BitSet bitlist;
21
22
public CombSubset(int total, int subnum) {
23 n = total;
24 m = subnum;
25 numset = Calfactorical(n) / (Calfactorical(m) * Calfactorical(n - m)); // The
26 // number
27 // of
28 // subsets
29 // System.out.println(numset);
30 while (n < m) {
31 System.out
32 .println("Wrong arguments!! Attention subset size <= total set size !!\n");
33 System.exit(1);
34
}
35 init = new int[n];
36 for (int i = 1; i <= n; i++)
37 init[i - 1] = i;
38 end = new int[numset][m];
39 relstr = new String[numset];
40 for (int i = 0; i < numset; i++)
41 relstr[i] = "";
42 }
43
44 public CombSubset(int subnum, int[] set) {
45 n = set.length;
46 m = subnum;
47 init = set;
48 numset = Calfactorical(n) / (Calfactorical(m) * Calfactorical(n - m)); // The
49 // number
50 // of
51 // subsets
52 while (n < m) {
53 System.out
54 .println("Wrong arguments!! Attention subset size <= total set size !!\n");
55 System.exit(1);
56 }
57 end = new int[numset][m];
58 left = new int[numset][n - m];
59 relstr = new String[numset];
60 leftstr = new String[numset];
61 for (int i = 0; i < numset; i++) {
62 relstr[i] = "";
63 leftstr[i] = "";
64 }
65 int[] index = new int[m];
66 count = 0;
67 bitlist = new BitSet(n);
68 ConstructCSubset(n, m, index);
69 }
70
71 public void ConstructSubset() {
72 int trace = 0;
73 int count = 0;
74 int[] temp = new int[m];
75 for (int i = 0; i < n;) {
76 if (n - i == m - trace) {
77 for (int j = 0; j < m - trace; j++)
78 temp[trace + j] = init[i + j];
79 for (int j = 0; j < m; j++) {
80 end[count][j] = temp[j];
81 String tmpstr = Integer.toString(temp[j]);
82 relstr[count] += tmpstr;
83 }
84 count++;
85 if (trace == 0)
86 break;
87 i = temp[--trace];
88 } else if (trace == m) {
89 for (int j = 0; j < m; j++) {
90 end[count][j] = temp[j];
91 String tmpstr = Integer.toString(temp[j]);
92 relstr[count] += tmpstr;
93 }
94 count++;
95 i = temp[--trace];
96 } else
97 temp[trace++] = init[i++];
98 }
99 }
100
101 public void ConstructCSubset(int num, int numflag, int[] index) { // int
102 // []index
103 // ,int
104 // step
105
106 for (int i = num; i >= numflag; i--) {
107 index[numflag - 1] = i - 1;
108 if (numflag > 1)
109 ConstructCSubset(i - 1, numflag - 1, index);
110 else {
111 for (int j = m - 1; j >= 0; j--) {
112 end[count][j] = init[index[j]];
113 String tmpstr = Integer.toString(init[index[j]]);
114 relstr[count] = tmpstr + relstr[count];
115 bitlist.set(index[j]); // Set the bit of the position true
116 }
117 for (int j = 0, k = 0; j < n; j++) {
118 if (!bitlist.get(j)) {
119 left[count][k++] = init[j];
120 String tmpstr = Integer.toString(init[j]);
121 leftstr[count] += tmpstr;
122 }
123 }
124 count++;
125 bitlist.clear(); // Set all bits false
126 }
127 }
128
129 }
130
131 /** *//** return the subsets **/
132
133 public int[][] getSubset() {
134 return end;
135 }
136
137 /** *//** return the left subsets **/
138
139 public int[][] getLeftset() {
140 return left;
141 }
142
143 /** *//** return the subsets string **/
144
145 public String[] getSubsetstr() {
146 return relstr;
147 }
148
149 /** *//** return the left subsets string **/
150
151 public String[] getLeftsetstr() {
152 return leftstr;
153 }
154
155 public int GetNumset() {
156 return numset;
157 }
158
159 public int Calfactorical(int num) {
160 int m = 1;
161 for (int i = 1; i <= num; i++)
162 m = m * i;
163 return m;
164 }
165
}
166