1 | package geniusweb.ip.general;
|
---|
2 |
|
---|
3 | import java.util.Arrays;
|
---|
4 | import java.util.Random;
|
---|
5 |
|
---|
6 | public class SubsetsOfMultiset {
|
---|
7 | final private ElementOfMultiset[] multiset; // The multiset from which we
|
---|
8 | // want to take subsets
|
---|
9 |
|
---|
10 | final private int sizeOfSubsets; // the size of the desired subsets
|
---|
11 |
|
---|
12 | private int totalNumOfElementsInMultiset; // the total number of elements
|
---|
13 | // (including repetitions)
|
---|
14 |
|
---|
15 | private ElementOfMultiset[] multisetWithIncrementalElements; // for example,
|
---|
16 | // if
|
---|
17 | // multiset = [2,2,2,5,5,6], then multisetWithIncrementalElements =
|
---|
18 | // [1,1,1,2,2,3]
|
---|
19 |
|
---|
20 | private boolean currentSubsetIsFirstSubset; // if "true", then the method
|
---|
21 | // "getNextSubset" would
|
---|
22 | // return the first subset in the list of subsets of
|
---|
23 | // "multisetWithIncrementalElements"
|
---|
24 |
|
---|
25 | private ElementOfMultiset[] currentSubset; // current subset in the list of
|
---|
26 | // subsets of
|
---|
27 | // "multisetWithIncrementalElements"
|
---|
28 |
|
---|
29 | private int numOfUniqueElementsInCurrentSubset; // the number of unique
|
---|
30 | // elements in the current
|
---|
31 | // subset. this
|
---|
32 | // should be updated every time "currentSubset" is changed
|
---|
33 |
|
---|
34 | /*
|
---|
35 | * if multisetWithIncrementalElements = [1,1,1,2,2,3], and sizeOfSubset=4,
|
---|
36 | * then then lastSubset = [1,2,2,3]
|
---|
37 | */
|
---|
38 | private ElementOfMultiset[] lastSubset;
|
---|
39 |
|
---|
40 | /*
|
---|
41 | * For every element in the current subset, this array contains the number
|
---|
42 | * of copies of that element that did not appear in the subset. For example,
|
---|
43 | * if multiset = [1,1,1,1,2,2,2,3,3,3,4,4,4], and the current subset is
|
---|
44 | * [1,1,3,3,4], then this method returns [2,1,2]. This is because the
|
---|
45 | * numbers of instances outside the current subset are: 2 for element "1", 1
|
---|
46 | * for element "3", and 2 for element "4"
|
---|
47 | */
|
---|
48 | private int[] numOfInstancesOutsideSubset;
|
---|
49 |
|
---|
50 | /*
|
---|
51 | * if "true" then for every element "e" in the current subset, the
|
---|
52 | * "SubsetOfMultiset" object will keep track of how many the object will
|
---|
53 | * keep track of how many instances of "e" were left out of the current
|
---|
54 | * subset.
|
---|
55 | */
|
---|
56 | private final boolean keepTrackOfNumOfInstancesOutsideSubset;
|
---|
57 |
|
---|
58 | // ************************************************************************************************
|
---|
59 |
|
---|
60 | /**
|
---|
61 | * The constructor
|
---|
62 | *
|
---|
63 | * @param multiset the multiset
|
---|
64 | * @param sizeOfSubsets the sizes of the required
|
---|
65 | * subsets
|
---|
66 | * @param keepTrackOfNumOfInstancesOutsideSubset if "true" then for every
|
---|
67 | * element "e" in the current
|
---|
68 | * subset, the
|
---|
69 | * "SubsetOfMultiset" object
|
---|
70 | * will keep track of how many
|
---|
71 | * the object will keep track
|
---|
72 | * of how many instances of
|
---|
73 | * "e" were left out of the
|
---|
74 | * current subset.
|
---|
75 | */
|
---|
76 | public SubsetsOfMultiset(ElementOfMultiset[] multiset, int sizeOfSubsets,
|
---|
77 | boolean keepTrackOfNumOfInstancesOutsideSubset) {
|
---|
78 | // Initialise
|
---|
79 | this.multiset = multiset;
|
---|
80 | this.sizeOfSubsets = sizeOfSubsets;
|
---|
81 | this.keepTrackOfNumOfInstancesOutsideSubset = keepTrackOfNumOfInstancesOutsideSubset;
|
---|
82 | resetParameters();
|
---|
83 | }
|
---|
84 |
|
---|
85 | // *********************************************************************************************************
|
---|
86 |
|
---|
87 | /**
|
---|
88 | * resets all parameters (used mainly in the constructor)
|
---|
89 | */
|
---|
90 | public void resetParameters() {
|
---|
91 | currentSubsetIsFirstSubset = true;
|
---|
92 |
|
---|
93 | multisetWithIncrementalElements = new ElementOfMultiset[multiset.length];
|
---|
94 | for (int i = 0; i < multiset.length; i++) {
|
---|
95 | multisetWithIncrementalElements[i] = new ElementOfMultiset(i + 1,
|
---|
96 | multiset[i].repetition);
|
---|
97 | }
|
---|
98 | setLastSubset();
|
---|
99 | currentSubset = new ElementOfMultiset[multiset.length];
|
---|
100 |
|
---|
101 | // Compute the total number of agents
|
---|
102 | totalNumOfElementsInMultiset = 0;
|
---|
103 | for (int i = 0; i < multiset.length; i++) {
|
---|
104 | totalNumOfElementsInMultiset += multiset[i].repetition;
|
---|
105 | }
|
---|
106 | }
|
---|
107 |
|
---|
108 | // *********************************************************************************************************
|
---|
109 |
|
---|
110 | /**
|
---|
111 | * An example of how to use this class (just for testing)...
|
---|
112 | */
|
---|
113 | public static void main(String[] args) {
|
---|
114 | // Create a test case, which is multiset = [4,4,4,5,5,6]
|
---|
115 | ElementOfMultiset[] multiset = new ElementOfMultiset[3];
|
---|
116 | multiset[0] = new ElementOfMultiset(4, 3);
|
---|
117 | multiset[1] = new ElementOfMultiset(5, 2);
|
---|
118 | multiset[2] = new ElementOfMultiset(6, 1);
|
---|
119 |
|
---|
120 | // enumerate all subsets of size = 1, 2, 3, ...
|
---|
121 | for (int size = 1; size <= 3; size++) {
|
---|
122 | System.out.println("Current size is " + size);
|
---|
123 | SubsetsOfMultiset subsetsOfMultiset = new SubsetsOfMultiset(
|
---|
124 | multiset, size, true);
|
---|
125 | ElementOfMultiset[] subset = subsetsOfMultiset.getNextSubset();
|
---|
126 | while (subset != null) {
|
---|
127 | // Put here the code that needs to deal with "subset", e.g.,
|
---|
128 | // printing it as below:
|
---|
129 | System.out.println("the current subset is "
|
---|
130 | + General.convertMultisetToString(subset)
|
---|
131 | + " , and numOfInstancesOutsideSubset = "
|
---|
132 | + Arrays.toString(subsetsOfMultiset
|
---|
133 | .getNumOfInstancesOutsideSubset()));
|
---|
134 | subset = subsetsOfMultiset.getNextSubset();
|
---|
135 | }
|
---|
136 | }
|
---|
137 | }
|
---|
138 |
|
---|
139 | // *********************************************************************************************************
|
---|
140 |
|
---|
141 | /**
|
---|
142 | * Given a subset S of a multiset, this method returns the subset S' that is
|
---|
143 | * located just before S in the list of subsets of the same size. Here, the
|
---|
144 | * list is ordered lexicographically.
|
---|
145 | */
|
---|
146 | public ElementOfMultiset[] getNextSubset() {
|
---|
147 | if (currentSubsetIsFirstSubset) {
|
---|
148 | setCurrentSubsetToFirstSubset();
|
---|
149 | currentSubsetIsFirstSubset = false;
|
---|
150 | return (prepareResult());
|
---|
151 | } else // If the required subset is not the first subset
|
---|
152 | {
|
---|
153 | int totalNumberOfElementsSeenSoFar = 0;
|
---|
154 | int indexInLastSubset = lastSubset.length - 1;
|
---|
155 | for (int indexInCurrentSubset = numOfUniqueElementsInCurrentSubset
|
---|
156 | - 1; indexInCurrentSubset >= 0; indexInCurrentSubset--) {
|
---|
157 | if (currentSubset[indexInCurrentSubset].element != lastSubset[indexInLastSubset].element) {
|
---|
158 | // remove one copy from the CURRENT unique agent, and
|
---|
159 | // replace it with a copy of the NEXT unique agent
|
---|
160 | if (currentSubset[indexInCurrentSubset].repetition > 1) {
|
---|
161 | currentSubset[indexInCurrentSubset].repetition--;
|
---|
162 | currentSubset[indexInCurrentSubset
|
---|
163 | + 1].element = currentSubset[indexInCurrentSubset].element
|
---|
164 | + 1;
|
---|
165 | currentSubset[indexInCurrentSubset + 1].repetition = 1;
|
---|
166 | numOfUniqueElementsInCurrentSubset++;
|
---|
167 | fillRemainingAgents(totalNumberOfElementsSeenSoFar,
|
---|
168 | indexInCurrentSubset + 1);
|
---|
169 | } else {
|
---|
170 | currentSubset[indexInCurrentSubset].element++;
|
---|
171 | fillRemainingAgents(totalNumberOfElementsSeenSoFar,
|
---|
172 | indexInCurrentSubset);
|
---|
173 | }
|
---|
174 | return (prepareResult());
|
---|
175 | } else {
|
---|
176 | if (currentSubset[indexInCurrentSubset].repetition < lastSubset[indexInLastSubset].repetition) {
|
---|
177 | totalNumberOfElementsSeenSoFar += currentSubset[indexInCurrentSubset].repetition;
|
---|
178 | numOfUniqueElementsInCurrentSubset--;
|
---|
179 | indexInCurrentSubset--;
|
---|
180 |
|
---|
181 | // remove one copy from the CURRENT unique agent, and
|
---|
182 | // replace it with a copy of the NEXT unique agent
|
---|
183 | if (currentSubset[indexInCurrentSubset].repetition > 1) {
|
---|
184 | currentSubset[indexInCurrentSubset].repetition--;
|
---|
185 | currentSubset[indexInCurrentSubset
|
---|
186 | + 1].element = currentSubset[indexInCurrentSubset].element
|
---|
187 | + 1;
|
---|
188 | currentSubset[indexInCurrentSubset
|
---|
189 | + 1].repetition = 1;
|
---|
190 | numOfUniqueElementsInCurrentSubset++;
|
---|
191 | fillRemainingAgents(totalNumberOfElementsSeenSoFar,
|
---|
192 | indexInCurrentSubset + 1);
|
---|
193 | } else {
|
---|
194 | currentSubset[indexInCurrentSubset].element++;
|
---|
195 | fillRemainingAgents(totalNumberOfElementsSeenSoFar,
|
---|
196 | indexInCurrentSubset);
|
---|
197 | }
|
---|
198 | return (prepareResult());
|
---|
199 | } else {
|
---|
200 | totalNumberOfElementsSeenSoFar += currentSubset[indexInCurrentSubset].repetition;
|
---|
201 | indexInLastSubset--;
|
---|
202 | numOfUniqueElementsInCurrentSubset--;
|
---|
203 | }
|
---|
204 | }
|
---|
205 | }
|
---|
206 | return (null);
|
---|
207 | }
|
---|
208 | }
|
---|
209 |
|
---|
210 | // ************************************************************************************************
|
---|
211 |
|
---|
212 | /**
|
---|
213 | * fills the remaining agents in a sequence, e.g., if we have 5 copies of
|
---|
214 | * agent 2, 5 copies of agent 3, and 3 copies of agent 4, and we want to
|
---|
215 | * fill 8 agents, then we put 5 copies of agent 2, and 3 copies of agent 3
|
---|
216 | */
|
---|
217 | private void fillRemainingAgents(int totalNumOfAgentsToBeAdded,
|
---|
218 | int indexAtWhichToStartFilling) {
|
---|
219 | if (totalNumOfAgentsToBeAdded == 0) {
|
---|
220 | return;
|
---|
221 | }
|
---|
222 | int firstUniqueAgentToBeAdded = currentSubset[indexAtWhichToStartFilling].element;
|
---|
223 |
|
---|
224 | // deal with the first index at which we need to fill elements
|
---|
225 | int max = multisetWithIncrementalElements[firstUniqueAgentToBeAdded
|
---|
226 | - 1].repetition
|
---|
227 | - currentSubset[indexAtWhichToStartFilling].repetition;
|
---|
228 | if (max > 0) {
|
---|
229 | if (totalNumOfAgentsToBeAdded <= max) {
|
---|
230 | currentSubset[indexAtWhichToStartFilling].repetition += totalNumOfAgentsToBeAdded;
|
---|
231 | return;
|
---|
232 | } else {
|
---|
233 | currentSubset[indexAtWhichToStartFilling].repetition += max;
|
---|
234 | totalNumOfAgentsToBeAdded -= max;
|
---|
235 | }
|
---|
236 | }
|
---|
237 | // deal with the remaining indices at which we need to fill the
|
---|
238 | // remaining elements
|
---|
239 | int k = 1;
|
---|
240 | do {
|
---|
241 | numOfUniqueElementsInCurrentSubset++;
|
---|
242 | if (totalNumOfAgentsToBeAdded <= multisetWithIncrementalElements[firstUniqueAgentToBeAdded
|
---|
243 | + k - 1].repetition) {
|
---|
244 | currentSubset[k
|
---|
245 | + indexAtWhichToStartFilling] = new ElementOfMultiset(
|
---|
246 | firstUniqueAgentToBeAdded + k,
|
---|
247 | totalNumOfAgentsToBeAdded);
|
---|
248 | break;
|
---|
249 | } else {
|
---|
250 | currentSubset[k
|
---|
251 | + indexAtWhichToStartFilling] = new ElementOfMultiset(
|
---|
252 | firstUniqueAgentToBeAdded + k,
|
---|
253 | multisetWithIncrementalElements[firstUniqueAgentToBeAdded
|
---|
254 | + k - 1].repetition);
|
---|
255 | totalNumOfAgentsToBeAdded -= multisetWithIncrementalElements[firstUniqueAgentToBeAdded
|
---|
256 | + k - 1].repetition;
|
---|
257 | k++;
|
---|
258 | }
|
---|
259 | } while (true);
|
---|
260 | }
|
---|
261 |
|
---|
262 | // ************************************************************************************************
|
---|
263 |
|
---|
264 | /**
|
---|
265 | * If multiset = [2,2,2,5,5,6], then multisetWithIncrementalElements =
|
---|
266 | * [1,1,1,2,2,3]. We generate subsets of [1,1,1,2,2,3] and not
|
---|
267 | * [2,2,2,5,5,6]. Then, before returning each subset, we convert it to the
|
---|
268 | * original elements. For example, if subset=[1,2,2], then after calling
|
---|
269 | * "prepareResult" we have subsetWithOriginalElements = [2,5,5].
|
---|
270 | */
|
---|
271 | private ElementOfMultiset[] prepareResult() {
|
---|
272 | // Initialization
|
---|
273 | ElementOfMultiset[] subsetWithOriginalElements = new ElementOfMultiset[numOfUniqueElementsInCurrentSubset];
|
---|
274 | if (keepTrackOfNumOfInstancesOutsideSubset) {
|
---|
275 | numOfInstancesOutsideSubset = new int[numOfUniqueElementsInCurrentSubset];
|
---|
276 | }
|
---|
277 |
|
---|
278 | for (int i = 0; i < numOfUniqueElementsInCurrentSubset; i++) {
|
---|
279 | ElementOfMultiset originalElement = multiset[currentSubset[i].element
|
---|
280 | - 1];
|
---|
281 | subsetWithOriginalElements[i] = new ElementOfMultiset(
|
---|
282 | originalElement.element, currentSubset[i].repetition);
|
---|
283 |
|
---|
284 | if (keepTrackOfNumOfInstancesOutsideSubset) {
|
---|
285 | numOfInstancesOutsideSubset[i] = originalElement.repetition
|
---|
286 | - currentSubset[i].repetition;
|
---|
287 | }
|
---|
288 | }
|
---|
289 | return (subsetWithOriginalElements);
|
---|
290 | }
|
---|
291 |
|
---|
292 | // ************************************************************************************************
|
---|
293 |
|
---|
294 | /**
|
---|
295 | * Returns the first subset in the list, e.g., for
|
---|
296 | * multisetWithIncrementalElements=[1,1,1,2,2,3], the first subset of size 4
|
---|
297 | * is [1,1,1,2]
|
---|
298 | */
|
---|
299 | private void setCurrentSubsetToFirstSubset() {
|
---|
300 | // Initialize the size of the first subset to the size of the multiset,
|
---|
301 | // because the
|
---|
302 | // number of unique elements in first subset is AT MOST equal to the
|
---|
303 | // size of the multiset.
|
---|
304 | currentSubset = new ElementOfMultiset[multisetWithIncrementalElements.length];
|
---|
305 | for (int i = 0; i < currentSubset.length; i++) {
|
---|
306 | currentSubset[i] = new ElementOfMultiset(0, 0);
|
---|
307 | }
|
---|
308 | // Initialize "numOfInstancesOutsideSubset" if necessary
|
---|
309 | if (keepTrackOfNumOfInstancesOutsideSubset)
|
---|
310 | numOfInstancesOutsideSubset = new int[multisetWithIncrementalElements.length];
|
---|
311 |
|
---|
312 | int totalNumOfAgentsToBeAdded = sizeOfSubsets;
|
---|
313 | int i = 0;
|
---|
314 | for (int j = 0; j < multisetWithIncrementalElements.length; j++) {
|
---|
315 | if (totalNumOfAgentsToBeAdded <= multisetWithIncrementalElements[j].repetition) {
|
---|
316 | currentSubset[i] = new ElementOfMultiset(
|
---|
317 | multisetWithIncrementalElements[j].element,
|
---|
318 | totalNumOfAgentsToBeAdded);
|
---|
319 | // Update "numOfInstancesOutsideSubset" if necessary
|
---|
320 | if (keepTrackOfNumOfInstancesOutsideSubset) {
|
---|
321 | numOfInstancesOutsideSubset[i] = multisetWithIncrementalElements[j].repetition
|
---|
322 | - totalNumOfAgentsToBeAdded;
|
---|
323 | }
|
---|
324 | break;
|
---|
325 | } else {
|
---|
326 | currentSubset[i] = new ElementOfMultiset(
|
---|
327 | multisetWithIncrementalElements[j].element,
|
---|
328 | multisetWithIncrementalElements[j].repetition);
|
---|
329 | totalNumOfAgentsToBeAdded -= multisetWithIncrementalElements[j].repetition;
|
---|
330 | i++;
|
---|
331 | // Update "numOfInstancesOutsideSubset" if necessary
|
---|
332 | if (keepTrackOfNumOfInstancesOutsideSubset) {
|
---|
333 | numOfInstancesOutsideSubset[i] = 0;
|
---|
334 | }
|
---|
335 | }
|
---|
336 | }
|
---|
337 | numOfUniqueElementsInCurrentSubset = i + 1;
|
---|
338 | }
|
---|
339 |
|
---|
340 | // ************************************************************************************************
|
---|
341 |
|
---|
342 | /**
|
---|
343 | * Returns the first subset in the list, e.g., for
|
---|
344 | * multisetWithIncrementalElements=[1,1,1,2,2,3], the first subset of size 4
|
---|
345 | * is [1,1,1,2]
|
---|
346 | */
|
---|
347 | private void setLastSubset() {
|
---|
348 | // Initialize the size of the last subset to "sizeOfSubsets", because
|
---|
349 | // the
|
---|
350 | // number of unique elements in last subset is AT MOST "sizeOfSubsets".
|
---|
351 | ElementOfMultiset[] temp = new ElementOfMultiset[multisetWithIncrementalElements.length];
|
---|
352 | for (int i = 0; i < temp.length; i++)
|
---|
353 | temp[i] = new ElementOfMultiset(0, 0);
|
---|
354 |
|
---|
355 | int totalNumOfAgentsToBeAdded = sizeOfSubsets;
|
---|
356 | int i = temp.length - 1;
|
---|
357 | for (int j = multisetWithIncrementalElements.length - 1; j >= 0; j--) {
|
---|
358 | if (totalNumOfAgentsToBeAdded <= multisetWithIncrementalElements[j].repetition) {
|
---|
359 | temp[i] = new ElementOfMultiset(
|
---|
360 | multisetWithIncrementalElements[j].element,
|
---|
361 | totalNumOfAgentsToBeAdded);
|
---|
362 | break;
|
---|
363 | } else {
|
---|
364 | temp[i] = new ElementOfMultiset(
|
---|
365 | multisetWithIncrementalElements[j].element,
|
---|
366 | multisetWithIncrementalElements[j].repetition);
|
---|
367 | totalNumOfAgentsToBeAdded -= multisetWithIncrementalElements[j].repetition;
|
---|
368 | i--;
|
---|
369 | }
|
---|
370 | }
|
---|
371 | // fill the elements of "temp" in "lastSubset"
|
---|
372 | lastSubset = new ElementOfMultiset[multisetWithIncrementalElements.length
|
---|
373 | - i];
|
---|
374 | for (int j = lastSubset.length - 1; j >= 0; j--)
|
---|
375 | lastSubset[j] = temp[temp.length - lastSubset.length + j];
|
---|
376 | }
|
---|
377 |
|
---|
378 | // *********************************************************************************************************
|
---|
379 |
|
---|
380 | /**
|
---|
381 | * For every element in the current subset, this method returns the number
|
---|
382 | * of copies of that element that did not appear in the subset
|
---|
383 | *
|
---|
384 | * For example, if multiset = [1,1,1,1,2,2,2,3,3,3,4,4,4], and the current
|
---|
385 | * subset is [1,1,3,3,4], then this method returns [2,1,2]. This is because
|
---|
386 | * the numbers of instances outside the current subset are: 2 for element
|
---|
387 | * "1", 1 for element "3", and 2 for element "4"
|
---|
388 | */
|
---|
389 | public int[] getNumOfInstancesOutsideSubset() {
|
---|
390 | if (keepTrackOfNumOfInstancesOutsideSubset)
|
---|
391 | return (numOfInstancesOutsideSubset);
|
---|
392 | else {
|
---|
393 | System.err.println(
|
---|
394 | "the method getNumOfInstancesOutsideSubset was called while the"
|
---|
395 | + "parameter keepTrackOfNumOfInstancesOutsideSubset was set to false");
|
---|
396 | return (null);
|
---|
397 | }
|
---|
398 | }
|
---|
399 |
|
---|
400 | // ************************************************************************************************
|
---|
401 |
|
---|
402 | /**
|
---|
403 | * Returns a random subset of the multiset
|
---|
404 | */
|
---|
405 | public ElementOfMultiset[] getRandomSubset() {
|
---|
406 | // deal with the case where the input is incorrect.
|
---|
407 | if ((sizeOfSubsets <= 0)
|
---|
408 | || (sizeOfSubsets >= totalNumOfElementsInMultiset)) {
|
---|
409 | System.err.println(
|
---|
410 | "ERROR in method: getRandomSubset, the size of the desired subset must be between 1 and totalNumOfElements-1");
|
---|
411 | return (null);
|
---|
412 | }
|
---|
413 |
|
---|
414 | Random randomIndex = new Random();
|
---|
415 | Random randomRepetition = new Random();
|
---|
416 |
|
---|
417 | // To improve efficiency, if the size of the required subset is greater
|
---|
418 | // than "multiset.length/2", then
|
---|
419 | // we will generate a random subset of size "multiset.length -
|
---|
420 | // sizeOfSubset" instead of "sizeOfSubset"
|
---|
421 | int sizeThatWeWillConsider;
|
---|
422 | if (sizeOfSubsets <= totalNumOfElementsInMultiset / 2)
|
---|
423 | sizeThatWeWillConsider = sizeOfSubsets;
|
---|
424 | else
|
---|
425 | sizeThatWeWillConsider = totalNumOfElementsInMultiset
|
---|
426 | - sizeOfSubsets;
|
---|
427 |
|
---|
428 | // this array specifies the indices of unique elements that can still be
|
---|
429 | // added to the subset
|
---|
430 | int[] indicesOfElementsThatCanBeAdded = new int[multiset.length];
|
---|
431 |
|
---|
432 | // the number of times each unique element is repeated in the subset
|
---|
433 | int[] numOfRepetitionsInSubset = new int[multiset.length];
|
---|
434 |
|
---|
435 | // this specifies the maximum index that we can deal with in the array
|
---|
436 | // "indicesOfElementsThatCanBeAdded",
|
---|
437 | // i.e., we will only deal with: "indicesOfElementsThatCanBeAdded[ i ]"
|
---|
438 | // for all i < maxIndex.
|
---|
439 | int maxIndex = multiset.length;
|
---|
440 |
|
---|
441 | // initialization
|
---|
442 | for (int i = multiset.length - 1; i >= 0; i--) {
|
---|
443 | indicesOfElementsThatCanBeAdded[i] = i;
|
---|
444 | numOfRepetitionsInSubset[i] = 0;
|
---|
445 | }
|
---|
446 | // create the random subset of size = "sizeThatWeWillConsider"
|
---|
447 | int sizeOfSubsetSoFar = 0;
|
---|
448 | int numOfUniqueElementsInSubset = 0;
|
---|
449 | do {
|
---|
450 | // choose a random unique element
|
---|
451 | int i = randomIndex.nextInt(maxIndex);
|
---|
452 | int j = indicesOfElementsThatCanBeAdded[i];
|
---|
453 |
|
---|
454 | // choose a random number of repetitions for the unique element
|
---|
455 | // (here, the random number will exclude zero)
|
---|
456 | // int k = 1 + randomRepetition.nextInt( Math.min(
|
---|
457 | // sizeThatWeWillConsider - sizeOfSubsetSoFar ,
|
---|
458 | // multiset[j].repetition - numOfRepetitionsInSubset[j] ) );
|
---|
459 | int k = 1; /* To be Unbiased! */
|
---|
460 |
|
---|
461 | // Check if this is a new unique element in the subset
|
---|
462 | if (numOfRepetitionsInSubset[j] == 0)
|
---|
463 | numOfUniqueElementsInSubset++;
|
---|
464 |
|
---|
465 | // update the number of repetitions in the subset
|
---|
466 | numOfRepetitionsInSubset[j] += k;
|
---|
467 |
|
---|
468 | // update the size of the subset so far
|
---|
469 | sizeOfSubsetSoFar += k;
|
---|
470 |
|
---|
471 | // if the element cannot be added any more, get rid of it
|
---|
472 | if (numOfRepetitionsInSubset[j] == multiset[j].repetition) {
|
---|
473 | indicesOfElementsThatCanBeAdded[i] = indicesOfElementsThatCanBeAdded[maxIndex
|
---|
474 | - 1];
|
---|
475 | maxIndex--;
|
---|
476 | }
|
---|
477 | } while (sizeOfSubsetSoFar != sizeThatWeWillConsider);
|
---|
478 |
|
---|
479 | // Create the random subset based on "numOfRepetitionsInSubset"
|
---|
480 | //
|
---|
481 | // Note: As mentioned earlier, to improve efficiency, if the size of the
|
---|
482 | // required subset is
|
---|
483 | // greater than "multiset.length/2", then we would have generated a
|
---|
484 | // random subset of
|
---|
485 | // size: "multiset.length - sizeOfSubset" instead of "sizeOfSubset"
|
---|
486 | //
|
---|
487 | if (sizeOfSubsets <= totalNumOfElementsInMultiset / 2) {
|
---|
488 | // Intialize "numOfInstancesOutsideSubset" if necessary
|
---|
489 | if (keepTrackOfNumOfInstancesOutsideSubset)
|
---|
490 | numOfInstancesOutsideSubset = new int[numOfUniqueElementsInSubset];
|
---|
491 |
|
---|
492 | ElementOfMultiset[] subset = new ElementOfMultiset[numOfUniqueElementsInSubset];
|
---|
493 | int j = 0;
|
---|
494 | for (int i = 0; i < multiset.length; i++) {
|
---|
495 | if (numOfRepetitionsInSubset[i] > 0) {
|
---|
496 | subset[j] = new ElementOfMultiset(multiset[i].element,
|
---|
497 | numOfRepetitionsInSubset[i]);
|
---|
498 |
|
---|
499 | // Update "numOfInstancesOutsideSubset" if necessary
|
---|
500 | if (keepTrackOfNumOfInstancesOutsideSubset)
|
---|
501 | numOfInstancesOutsideSubset[j] = multiset[i].repetition
|
---|
502 | - numOfRepetitionsInSubset[i];
|
---|
503 |
|
---|
504 | j++;
|
---|
505 | if (j == subset.length) {
|
---|
506 | break;
|
---|
507 | }
|
---|
508 | }
|
---|
509 | }
|
---|
510 | return (subset);
|
---|
511 | } else {
|
---|
512 | // We initially allocate memory for a number of unique elements that
|
---|
513 | // is equal to "multiset.length".
|
---|
514 | // This is because the number of unique elements in the subset is at
|
---|
515 | // most "multiset.length"
|
---|
516 | ElementOfMultiset[] temp_subset = new ElementOfMultiset[multiset.length];
|
---|
517 | int[] temp_numOfInstancesOutsideSubset = new int[multiset.length];
|
---|
518 | int j = 0;
|
---|
519 | for (int i = 0; i < multiset.length; i++) {
|
---|
520 | if (numOfRepetitionsInSubset[i] < multiset[i].repetition) {
|
---|
521 | temp_subset[j] = new ElementOfMultiset(multiset[i].element,
|
---|
522 | multiset[i].repetition
|
---|
523 | - numOfRepetitionsInSubset[i]);
|
---|
524 |
|
---|
525 | // Update "numOfInstancesOutsideSubset" if necessary
|
---|
526 | if (keepTrackOfNumOfInstancesOutsideSubset)
|
---|
527 | temp_numOfInstancesOutsideSubset[j] = numOfRepetitionsInSubset[i];
|
---|
528 |
|
---|
529 | j++;
|
---|
530 | }
|
---|
531 | }
|
---|
532 | // truncate "temp_subset" and "temp_numOfInstanceOutsideSubset" to
|
---|
533 | // the desired length
|
---|
534 | ElementOfMultiset[] subset = new ElementOfMultiset[j];
|
---|
535 | numOfInstancesOutsideSubset = new int[j];
|
---|
536 | for (int i = 0; i < j; i++) {
|
---|
537 | subset[i] = temp_subset[i];
|
---|
538 | numOfInstancesOutsideSubset[i] = temp_numOfInstancesOutsideSubset[i];
|
---|
539 | }
|
---|
540 | return (subset);
|
---|
541 | }
|
---|
542 | }
|
---|
543 | } |
---|