source: ip/src/main/java/geniusweb/ip/general/SubsetsOfMultiset.java@ 52

Last change on this file since 52 was 52, checked in by ruud, 14 months ago

Fixed small issues in domaineditor.
File size: 20.5 KB
Line 
1package geniusweb.ip.general;
2
3import java.util.Arrays;
4import java.util.Random;
5
6public 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}
Note: See TracBrowser for help on using the repository browser.