source: ip/src/main/java/geniusweb/ip/general/IntegerPartition.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.4 KB
Line 
1package geniusweb.ip.general;
2
3public class IntegerPartition {
4 public int[] partsSortedAscendingly;
5 public int[] sortedMultiplicity;
6 public int[] sortedUnderlyingSet;
7 public int sortedUnderlyingSetInBitFormat;
8 public int numOfAgents;
9 public ElementOfMultiset[] sortedMultiset;
10 public int[] tempIntegersThatResultedFromASplit; // I use it occationally to
11 // store the two
12 // integers that were
13 // the result of a split
14
15 // *****************************************************************************************************
16
17 /**
18 * Constructor
19 */
20 public IntegerPartition(int[] parts) {
21 numOfAgents = 0;
22 for (int i = 0; i < parts.length; i++)
23 numOfAgents += parts[i];
24 partsSortedAscendingly = General.sortArray(parts, true);
25 sortedUnderlyingSet = General.getUnderlyingSet(partsSortedAscendingly);
26 sortedMultiplicity = new int[sortedUnderlyingSet.length];
27 int indexInMultiplicity = 0;
28 sortedMultiplicity[indexInMultiplicity] = 1;
29 for (int i = 1; i < partsSortedAscendingly.length; i++) {
30 if (partsSortedAscendingly[i] == partsSortedAscendingly[i - 1])
31 sortedMultiplicity[indexInMultiplicity]++;
32 else {
33 indexInMultiplicity++;
34 sortedMultiplicity[indexInMultiplicity] = 1;
35 }
36 }
37 sortedUnderlyingSetInBitFormat = Combinations
38 .convertCombinationFromByteToBitFormat(sortedUnderlyingSet);
39
40 // The integer partition represented concisely as a multiset
41 sortedMultiset = new ElementOfMultiset[sortedMultiplicity.length];
42 for (int i = 0; i < sortedMultiset.length; i++) {
43 sortedMultiset[i] = new ElementOfMultiset(sortedUnderlyingSet[i],
44 sortedMultiplicity[i]);
45 }
46 }
47
48 // *****************************************************************************************************
49
50 /**
51 * Returns the NUMBER of Integer partitions that are directly connected to
52 * this one (which are all in the above level of the integer partition
53 * graph).
54 */
55 public int getNumOfDirectedlyConnectedIntegerPartitions(
56 int largestIntegerBeingSplit, int prev_largestIntegerBeingSplit) {
57 // Check the special case where the node is the bottom one in the
58 // graph...
59 if (sortedUnderlyingSet[0] == numOfAgents)
60 return ((int) Math.floor(numOfAgents / (double) 2));
61
62 int counter = 0;
63 for (int i = 0; i < sortedUnderlyingSet.length; i++) {
64 if ((sortedUnderlyingSet[i] > largestIntegerBeingSplit)
65 || (sortedUnderlyingSet[i] <= prev_largestIntegerBeingSplit)) {
66 continue;
67 }
68 // for every possible way of splitting "underlyingSet[i]" into two
69 // integers
70 for (int j = 1; j <= (int) Math
71 .floor(sortedUnderlyingSet[i] / (double) 2); j++) {
72 int smallHalf = j;
73 int largeHalf = sortedUnderlyingSet[i] - j;
74 if (largeHalf > numOfAgents - smallHalf - largeHalf) {
75 continue;
76 }
77 counter++;
78 }
79 }
80 return (counter);
81 }
82
83 // *****************************************************************************************************
84
85 /**
86 * Returns the LIST of Integer partitions that are directly connected to
87 * this one (which are all in the above level of the integer partition
88 * graph).
89 */
90 public IntegerPartition[] getListOfDirectedlyConnectedIntegerPartitions(
91 int largestIntegerBeingSplit, int prev_largestIntegerBeingSplit) {
92 // Allocate memory for the list of directly connected integer partitions
93 int counter = getNumOfDirectedlyConnectedIntegerPartitions(
94 largestIntegerBeingSplit, prev_largestIntegerBeingSplit);
95 if (counter == 0) {
96 return (null);
97 }
98 IntegerPartition[] listOfDirectlyConnectedIntegerPartitions = new IntegerPartition[counter];
99
100 // Check the special case where the node is the bottom one in the graph
101 if (sortedUnderlyingSet[0] == numOfAgents) {
102 int index = 0;
103 for (int i = 1; i <= (int) Math
104 .floor(numOfAgents / (double) 2); i++) {
105 int[] newSortedParts = new int[2];
106 newSortedParts[0] = i;
107 newSortedParts[1] = numOfAgents - i;
108 listOfDirectlyConnectedIntegerPartitions[index] = new IntegerPartition(
109 newSortedParts);
110 listOfDirectlyConnectedIntegerPartitions[index].tempIntegersThatResultedFromASplit = new int[] {
111 i, numOfAgents - i };
112 index++;
113 }
114 } else {
115 // Compute the list of directly connected integer partitions
116 int index = 0;
117 for (int i = 0; i < sortedUnderlyingSet.length; i++) {
118 final int curPart = sortedUnderlyingSet[i];
119 if ((curPart > largestIntegerBeingSplit)
120 || (curPart <= prev_largestIntegerBeingSplit)) {
121 continue;
122 }
123 // for every possible way of splitting "curPart" into two
124 // integers
125 for (int j = 1; j <= (int) Math
126 .floor(curPart / (double) 2); j++) {
127 int smallHalf = j;
128 int largeHalf = curPart - j;
129 if (largeHalf > numOfAgents - smallHalf - largeHalf) {
130 continue;
131 }
132 int[] newSortedParts = new int[partsSortedAscendingly.length
133 + 1];
134 int i1 = 0;
135 int i2 = 0;
136 while (partsSortedAscendingly[i1] < smallHalf) {
137 newSortedParts[i2] = partsSortedAscendingly[i1];
138 i1++;
139 i2++;
140 }
141 newSortedParts[i2] = smallHalf;
142 i2++;
143 while (partsSortedAscendingly[i1] < largeHalf) {
144 newSortedParts[i2] = partsSortedAscendingly[i1];
145 i1++;
146 i2++;
147 }
148 newSortedParts[i2] = largeHalf;
149 i2++;
150 boolean curPartHasBeenSeen = false;
151 while (i1 < partsSortedAscendingly.length) {
152 if ((partsSortedAscendingly[i1] == curPart)
153 && (curPartHasBeenSeen == false)) {
154 curPartHasBeenSeen = true;
155 i1++;
156 } else {
157 newSortedParts[i2] = partsSortedAscendingly[i1];
158 i1++;
159 i2++;
160 }
161 }
162 listOfDirectlyConnectedIntegerPartitions[index] = new IntegerPartition(
163 newSortedParts);
164 listOfDirectlyConnectedIntegerPartitions[index].tempIntegersThatResultedFromASplit = new int[] {
165 smallHalf, largeHalf };
166 index++;
167 }
168 }
169 }
170 return (listOfDirectlyConnectedIntegerPartitions);
171 }
172
173 // *****************************************************************************************************
174
175 /**
176 * This method returns the number of integer partitions of "n"
177 */
178 public static int getNumOfIntegerPartitions(int n) {
179 int numOfIntegerPartitions = 0;
180 for (int level = 1; level <= n; level++) {
181 numOfIntegerPartitions += IntegerPartition
182 .getNumOfIntegerPartitionsInLevel(n, level);
183 }
184 return (numOfIntegerPartitions);
185 }
186
187 // ******************************************************************************************************
188
189 /**
190 * This method returns the number of integer partitions of "n" that are in
191 * level = "level" of the integer partition graph (i.e. those of size =
192 * "level")
193 */
194 public static int getNumOfIntegerPartitionsInLevel(int n, int level) {
195 return (getNumOfIntegerPartitionsInLevel_additionalParameter(n, level,
196 n - level + 1));
197 }
198
199 private static int getNumOfIntegerPartitionsInLevel_additionalParameter(
200 int n, int level, int M) {
201 if ((level == 1) || (level == n)) {
202 return (1);
203 }
204 int sum = 0;
205 for (int M1 = (int) Math.ceil(n / (double) level); M1 <= Math
206 .min(n - level + 1, M); M1++) {
207 sum += getNumOfIntegerPartitionsInLevel_additionalParameter(n - M1,
208 level - 1, M1);
209 }
210 return (sum);
211 }
212
213 // ******************************************************************************************************
214
215 /**
216 * This method returns the number of integer partitions of "n" that are in
217 * level = "level" of of the integer partition graph (i.e. those of size =
218 * "level"), where the smallest part in each partition is smaller than, or
219 * equal to, "smallestPart".
220 */
221 public static int getNumOfIntegerPartitionsInLevel(int n, int level,
222 int smallestPart) {
223 return (getNumOfIntegerPartitionsInLevel_additionalParameter(n, level,
224 smallestPart, n - level + 1));
225 }
226
227 private static int getNumOfIntegerPartitionsInLevel_additionalParameter(
228 int n, int level, int smallestPart, int M) {
229 if (smallestPart == 1) {
230 return (getNumOfIntegerPartitionsInLevel(n, level));
231 } else {
232 if ((n < smallestPart) || (level == n)) {
233 return (0);
234 }
235 if (level == 1) {
236 return (1);
237 }
238 int sum = 0;
239 for (int M1 = (int) Math.ceil(n / (double) level); M1 <= Math
240 .min(n - level + 1, M); M1++) {
241 sum += getNumOfIntegerPartitionsInLevel_additionalParameter(
242 n - M1, level - 1, smallestPart, M1);
243 }
244 return (sum);
245 }
246 }
247
248 // ******************************************************************************************************
249
250 /**
251 * This method generates the integer partitions of n; it uses the algorithm
252 * SZ1. For more details, see: "Fast algorithms for generating integer
253 * partitions", by Antoine Zoghbi and Ivan Stojmenovic, 1998
254 */
255 public static int[][] getIntegerPartitionsOrderedLexicographically(int n,
256 boolean orderIntegerPartitionsAscendingly) {
257 int index = 0;
258
259 // Memory allocation
260 int[][] listOfIntegerPartitions = new int[IntegerPartition
261 .getNumOfIntegerPartitions(n)][];
262
263 // Initialize "indexOfNewPartition". Here, "indexOfNewPartition[i]"
264 // represents the
265 // index at which any new partition with "i+1" parts must be added to
266 // integerPartitions[i].
267 int[] indexOfNewPartition = new int[n];
268 for (int i = 0; i < n; i++)
269 indexOfNewPartition[i] = 0;
270
271 // We will set x to one integer partition, and then to another, and so
272 // on, until we
273 // are done with all integer partitions.
274 // NOTE: I have made x contain n+1 element. This way, if we ignore the
275 // first element
276 // (i.e. x[0]) then the first element in x becomes x[1] just as in the
277 // paper.
278 //
279 int[] x = new int[n + 1];
280
281 // Setting x to the integer partition containing n parts, all of which
282 // have a value of 1.
283 for (int i = 1; i <= n; i++)
284 x[i] = 1;
285
286 // Initialization
287 x[1] = n;
288 int m = 1;
289 int h = 1;
290
291 // put the first integer partition in the list.
292 listOfIntegerPartitions[index] = new int[x.length];
293 for (int i = 0; i < x.length; i++)
294 listOfIntegerPartitions[index][i] = x[i];
295 index++;
296
297 // Setting x to the other integer partitions
298 while (x[1] != 1) {
299 if (x[h] == 2) {
300 m = m + 1;
301 x[h] = 1;
302 h = h - 1;
303 } else {
304 int r = x[h] - 1;
305 int t = m - h + 1;
306 x[h] = r;
307 while (t >= r) {
308 h = h + 1;
309 x[h] = r;
310 t = t - r;
311 }
312 if (t == 0) {
313 m = h;
314 } else {
315 m = h + 1;
316 if (t > 1) {
317 h = h + 1;
318 x[h] = t;
319 }
320 }
321 }
322 // put the current integer partition in the list.
323 listOfIntegerPartitions[index] = new int[x.length];
324 for (int i = 0; i < x.length; i++)
325 listOfIntegerPartitions[index][i] = x[i];
326 index++;
327 }
328 return (listOfIntegerPartitions);
329 }
330
331 // ******************************************************************************************************
332
333 /**
334 * This method generates the integer partitions of n; it uses the algorithm
335 * SZ1. For more details, see: "Fast algorithms for generating integer
336 * partitions", by Antoine Zoghbi and Ivan Stojmenovic, 1998
337 */
338 public static int[][][] getIntegerPartitions(int n,
339 boolean orderIntegerPartitionsAscendingly) {
340 // Memory allocation
341 int[][][] integerPartitions = allocateMemoryForIntegerPartitions(n);
342
343 // Initialize "indexOfNewPartition". Here, "indexOfNewPartition[i]"
344 // represents the
345 // index at which any new partition with "i+1" parts must be added to
346 // integerPartitions[i].
347 int[] indexOfNewPartition = new int[n];
348 for (int i = 0; i < n; i++)
349 indexOfNewPartition[i] = 0;
350
351 // We will set x to one integer partition, and then to another, and so
352 // on, until we
353 // are done with all integer partitions.
354 // NOTE: I have made x contain n+1 element. This way, if we ignore the
355 // first element
356 // (i.e. x[0]) then the first element in x becomes x[1] just as in the
357 // paper.
358 //
359 int[] x = new int[n + 1];
360
361 // Setting x to the integer partition containing n parts, all of which
362 // have a value of 1.
363 for (int i = 1; i <= n; i++)
364 x[i] = 1;
365
366 // Initialization
367 x[1] = n;
368 int m = 1;
369 int h = 1;
370 fill_x_in_partitions(x, integerPartitions, m,
371 orderIntegerPartitionsAscendingly, indexOfNewPartition);
372
373 // Setting x to the other integer partitions
374 while (x[1] != 1) {
375 if (x[h] == 2) {
376 m = m + 1;
377 x[h] = 1;
378 h = h - 1;
379 } else {
380 int r = x[h] - 1;
381 int t = m - h + 1;
382 x[h] = r;
383 while (t >= r) {
384 h = h + 1;
385 x[h] = r;
386 t = t - r;
387 }
388 if (t == 0) {
389 m = h;
390 } else {
391 m = h + 1;
392 if (t > 1) {
393 h = h + 1;
394 x[h] = t;
395 }
396 }
397 }
398 // This method fills x in the array "integerPartitions"
399 fill_x_in_partitions(x, integerPartitions, m,
400 orderIntegerPartitionsAscendingly, indexOfNewPartition);
401 }
402 return (integerPartitions);
403 }
404
405 // ******************************************************************************************************
406
407 /**
408 * This method generates all integer partitions of m in which every part is
409 * greater than, or equal to, l1. I also adds these partitions to the
410 * relevant layers in the array "prevPartitions" (based on the number of
411 * parts in each partition).
412 *
413 * This method uses the algorithm parta. For more details, see; "Algorithm
414 * 29 Efficient Algorithms for Double and Multiply Restricted Partitions",
415 * by W. Riha and K. R. James, 1974.
416 *
417 * Note the following differences between my code and the code of the
418 * original algorithm "parta"
419 *
420 * * I set parameter "z" to 0 (to avoid generating any partition that
421 * contains repeated parts, set z to 1). * I removed "num" since I won't be
422 * using it. * I added the parameter "carryOn" to avoid the use of "goto" *
423 * I replaced "proc" (which prints x) with "fill_x_in_partitions" (which
424 * adds x to "prevPartitions").
425 */
426 public static int[][][] getRestrictedIntegerPartitions(int m, int l1,
427 boolean ascending) {
428 // Memory allocation...
429 int[][][] integerPartitions = allocateMemoryForIntegerPartitions(m, l1);
430
431 // Initialize "indexOfNewPartition". Here, "indexOfNewPartition[i]"
432 // represents the
433 // index at which any new partition with "i+1" parts must be added to
434 // integerPartitionss[i].
435 int[] indexOfNewPartition = new int[m];
436 for (int i = 0; i < integerPartitions.length; i++)
437 indexOfNewPartition[i] = 0;
438
439 // Store the original value of m (this is because "parta" changes the
440 // value of "m" while running)
441 int original_m = m;
442
443 integerPartitions[0][0][0] = m;
444 for (int level = 2; level <= integerPartitions.length; level++) {
445 m = original_m; // Set "m" to its original value.
446 int n = level; // Set the number of parts.
447 int l2 = m; // Set the maximum value that a part in this level can
448 // get.
449 int z = 0;
450
451 // ********************************************
452 // *** ***
453 // *** The "parta" algorithm ***
454 // *** ***
455 // ********************************************
456
457 int i, j;
458 int[] x = new int[n + 1];
459 int[] y = new int[n + 1];
460 j = z * n * (n - 1);
461 m = m - n * l1 - j / 2;
462 l2 = l2 - l1;
463 if ((m >= 0) & (m <= n * l2 - j)) {
464 for (i = 1; i <= n; i++) {
465 x[i] = l1 + z * (n - i);
466 y[i] = l1 + z * (n - i);
467 }
468 i = 1;
469 l2 = l2 - z * (n - 1);
470
471 boolean carryOn = true;
472 while (carryOn) {
473 carryOn = false;
474 while (m > l2) {
475 m = m - l2;
476 x[i] = y[i] + l2;
477 i = i + 1;
478 }
479 x[i] = y[i] + m;
480 fill_x_in_partitions(x, integerPartitions, n, ascending,
481 indexOfNewPartition);
482 if ((i < n) & (m > 1)) {
483 m = 1;
484 x[i] = x[i] - 1;
485 i = i + 1;
486 x[i] = y[i] + 1;
487 fill_x_in_partitions(x, integerPartitions, n, ascending,
488 indexOfNewPartition);
489 }
490 for (j = i - 1; j >= 1; j--) {
491 l2 = x[j] - y[j] - 1;
492 m = m + 1;
493 if (m <= (n - j) * l2) {
494 x[j] = y[j] + l2;
495 carryOn = true;
496 break;
497 }
498 m = m + l2;
499 x[i] = y[i];
500 i = j;
501 }
502 }
503 }
504 }
505 return (integerPartitions);
506 }
507
508 // ******************************************************************************************************
509
510 /**
511 * This is only used in the method "getIntegerPartitions". It allocates the
512 * memory required for the array of integer partitions.
513 */
514 private static int[][][] allocateMemoryForIntegerPartitions(int n) {
515 // Count the number of integerPartitionss in each level
516 int[] numOfIntegerPartitionsInLevel = new int[n];
517 for (int level = 1; level <= n; level++)
518 numOfIntegerPartitionsInLevel[level
519 - 1] = getNumOfIntegerPartitionsInLevel(n, level);
520
521 int[][][] integerPartitions = new int[n][][];
522 for (int level = 1; level <= n; level++) {
523 integerPartitions[level
524 - 1] = new int[numOfIntegerPartitionsInLevel[level - 1]][];
525 for (int i = 0; i < numOfIntegerPartitionsInLevel[level - 1]; i++) {
526 integerPartitions[level - 1][i] = new int[level];
527 }
528 }
529 return (integerPartitions);
530 }
531
532 // ******************************************************************************************************
533
534 /**
535 * This is only used in the method "generateRestrictedIntegerPartitions". It
536 * allocates the memory required for the array of integer partitions of "n"
537 * in which the parts are greater than, or equal to, "smallestPart".
538 */
539 private static int[][][] allocateMemoryForIntegerPartitions(int n,
540 int smallestPart) {
541 // Count the number of integer partitions in each level, as well as the
542 // number of non-empty levels.
543 int numOfNonEmptyLevels = 0;
544 int[] numOfIntegerPartitions = new int[n];
545 for (int level = 1; level <= n; level++) {
546 numOfIntegerPartitions[level
547 - 1] = getNumOfIntegerPartitionsInLevel(n, level,
548 smallestPart);
549 if (numOfIntegerPartitions[level - 1] > 0) {
550 numOfNonEmptyLevels++;
551 }
552 }
553
554 int[][][] integerPartitions = new int[numOfNonEmptyLevels][][];
555 for (int level = 1; level <= numOfNonEmptyLevels; level++) {
556 integerPartitions[level
557 - 1] = new int[numOfIntegerPartitions[level - 1]][];
558 for (int i = 0; i < numOfIntegerPartitions[level - 1]; i++) {
559 integerPartitions[level - 1][i] = new int[level];
560 }
561 }
562 return (integerPartitions);
563 }
564
565 // ******************************************************************************************************
566
567 /**
568 * This is only used in the methods: "getIntegerPartitions" (which uses the
569 * SZ1 algorithm) and the method: "generateRestrictedIntegerPartitions"
570 * (which uses the parta algorithm).
571 *
572 * It fills x (i.e. the current integer partitoin) in the array
573 * "integerPartitions".
574 */
575 private static void fill_x_in_partitions(int x[],
576 int[][][] integerPartitions, int m, boolean ascending,
577 int[] indexOfNewPartition) {
578 // Note that the integer partition in x is ordered in a descending
579 // order. However, we
580 // might want to fill in "integerPartitions" in an ascending order.
581 if (ascending == false) {
582 for (int i = 1; i <= m; i++)
583 integerPartitions[m - 1][indexOfNewPartition[m - 1]][i
584 - 1] = x[i];
585 indexOfNewPartition[m - 1]++;
586 } else // fill x in "integerPartitions" such that the elements in
587 // "integerPartitions" are ordered ascendingly
588 {
589 for (int i = 1; i <= m; i++)
590 integerPartitions[m - 1][indexOfNewPartition[m - 1]][i
591 - 1] = x[m - i + 1];
592 indexOfNewPartition[m - 1]++;
593 }
594 }
595
596 // ******************************************************************************************************
597
598 /**
599 * This method sorts the integer partitions lexicographically. For example,
600 * [3,3,2,2,1], [3,3,2,1,1,1], [3,3,3,2], [4,1] will be sorted as follows:
601 * [4,1] [3,3,3,2] [3,3,2,2,1] [3,3,2,1,1,1] Also: [1,2,2,3,3],
602 * [1,1,1,2,3,3], [2,3,3,3], [1,4] will be sorted as follows: [2,3,3,3]
603 * [1,4] [1,2,2,3,3] [1,1,1,2,3,3]
604 *
605 * @return list of indices of the new order. In example 1, it returns
606 * [2,3,1,0]. In example 2, it returns [2,3,0,1]
607 */
608 public static int[] sortListOfIntegerPartitionsLexicographically(
609 int[][] listOfIntegerPartitions,
610 boolean eachIntegerPartitionIsOrderedAscendingly) {
611 int[] sortedIndices = new int[listOfIntegerPartitions.length];
612
613 return (sortedIndices);
614 }
615
616 // ******************************************************************************************************
617
618 /**
619 * returns true if the integer partition contains the given multiset.
620 * Otherwise, it returns false
621 */
622 public boolean contains(ElementOfMultiset[] multiset) {
623 if (sortedMultiset.length < multiset.length)
624 return (false);
625
626 for (int i = 0; i < multiset.length; i++) {
627 boolean found = false;
628 for (int j = 0; j < this.sortedMultiset.length; j++) {
629 if (this.sortedMultiset[j].element == multiset[i].element) {
630 if (this.sortedMultiset[j].repetition < multiset[i].repetition) {
631 return (false);
632 }
633 found = true;
634 break;
635 }
636 }
637 if (found == false) {
638 return (false);
639 }
640 }
641 return (true);
642 }
643}
Note: See TracBrowser for help on using the repository browser.