[32] | 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 | } |
---|