source: ip/src/main/java/geniusweb/ip/general/Combinations.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: 29.9 KB
Line 
1package geniusweb.ip.general;
2
3import java.math.BigInteger;
4
5/**
6 * Class that contains general combinatorial functions such as computing the
7 * number of possible combinations of a set of a certain size, generating a list
8 * of the possible combinations, and so on...
9 *
10 * @author Talal Rahwan
11 */
12public class Combinations {
13 private static long[][] pascalMatrix = null;
14
15 // ******************************************************************************************************
16
17 /**
18 * This method initializes pascal�s Matrix. For more details, see "An
19 * Algorithm for Distributing Coalitional Value Calculations Among
20 * Cooperative Agents" [AIJ, 2007]
21 */
22 public static long[][] initPascalMatrix(int numOfLines, int numOfColumns) {
23 if ((pascalMatrix == null) || (numOfLines > pascalMatrix.length)) {
24 if (pascalMatrix == null) // Build the matrix from scratch
25 {
26 pascalMatrix = new long[numOfLines][numOfColumns];
27 for (int i = 0; i < numOfLines; i++) {
28 pascalMatrix[i][0] = 1;
29 }
30 for (int j = 1; j < numOfColumns; j++) {
31 pascalMatrix[0][j] = j + 1;
32 }
33
34 for (int i = 1; i < numOfLines; i++)
35 for (int j = 1; j < numOfColumns; j++)
36 pascalMatrix[i][j] = pascalMatrix[i - 1][j]
37 + pascalMatrix[i][j - 1];
38 } else // extend the already-built matrix (only if the previous one
39 // was smaller than the current one)
40 {
41 long[][] prev_pascalMatrix = pascalMatrix;
42 int prev_numOfLines = prev_pascalMatrix.length;
43 int prev_numOfColumns = prev_pascalMatrix[0].length;
44
45 pascalMatrix = new long[numOfLines][numOfColumns];
46 for (int i = 0; i < numOfLines; i++) {
47 pascalMatrix[i][0] = 1;
48 }
49 for (int j = 1; j < numOfColumns; j++) {
50 pascalMatrix[0][j] = j + 1;
51 }
52
53 for (int i = 1; i < prev_numOfLines; i++) {
54 // Copy the pervious columns of the previous lines
55 for (int j = 1; j < prev_numOfColumns; j++)
56 pascalMatrix[i][j] = prev_pascalMatrix[i][j];
57 // Add the new columns to the previous lines
58 for (int j = prev_numOfColumns; j < numOfColumns; j++)
59 pascalMatrix[i][j] = pascalMatrix[i - 1][j]
60 + pascalMatrix[i][j - 1];
61 ;
62 }
63 // Build the new lines
64 for (int i = prev_numOfLines; i < numOfLines; i++)
65 for (int j = 1; j < numOfColumns; j++)
66 pascalMatrix[i][j] = pascalMatrix[i - 1][j]
67 + pascalMatrix[i][j - 1];
68
69 // Free the previous matrix
70 prev_pascalMatrix = null;
71 }
72 }
73 return (pascalMatrix);
74 }
75
76 // ******************************************************************************************************
77
78 /**
79 * This function returns the number of combinations of size y out of x
80 * agents, In other words, it returns the following value: factorial(x) /
81 * factorial(x-y)*factorial(y)
82 */
83 public static long binomialCoefficient(int x, int y) {
84 if (x == y)
85 return (1); // Deal with this special case
86
87 // initialize pascal matrix (if it hasn't already been initialized)
88 initPascalMatrix(x, x);
89
90 // By this, we have: C^x_y = pascalMatrix[x-y-1,y] (with the exception
91 // of the case where n = m)
92 return (pascalMatrix[x - y - 1][y]);
93 /*
94 * //Alternative method... int result = 1; if( y > x / 2 ) y = (int)(x -
95 * y); for (int i = 1; i <= y; i++) result = result * (x + 1 - i) / i;
96 * return result;
97 */
98 }
99
100 // ******************************************************************************************************
101
102 /**
103 * Given a combination in bit format, return its size (i.e. the number of
104 * ones it contains)
105 */
106 public static int getSizeOfCombinationInBitFormat(
107 int combinationInBitFormat, int numOfAgents) {
108 return (Integer.bitCount(combinationInBitFormat));
109 /*
110 * int result = 0; for (int i = 0; i < numOfAgents; i++) if
111 * ((combinationInBitFormat & (1<<i)) != 0) //if agent "i+1" is a member
112 * of "combinationInBitFormat" result++;
113 *
114 * return result;
115 */
116 }
117
118 // ******************************************************************************************************
119
120 /**
121 * Compute the number of possible coalition structures.
122 */
123 public static long getNumOfCS(int numOfAgents) {
124 long numOfCS = 0;
125 for (int size = 1; size <= numOfAgents; size++)
126 numOfCS += Combinations.getNumOfCSOfCertainSize(numOfAgents, size);
127 return (numOfCS);
128 }
129
130 // The following is an alternative approach that uses "BigInteger"
131 public static BigInteger getNumOfCS_bitIntegerVersion(int numOfAgents) {
132 BigInteger numOfCS = BigInteger.valueOf(0);
133 for (int size = 1; size <= numOfAgents; size++)
134 numOfCS = numOfCS
135 .add(Combinations.getNumOfCSOfCertainSize_bigIntegerVersion(
136 numOfAgents, size));
137 return (numOfCS);
138 }
139
140 // ******************************************************************************************************
141
142 /**
143 * Compute the number of coalitions in the search space (i.e., in the space
144 * of possible coalition structure). Here, for every coalition structure, we
145 * count the number of coalitions in it.
146 */
147 public static long getNumOfCoalitionsInSearchSpace(int numOfAgents) {
148 long numOfCoalitionsInSearchSpace = 0;
149 for (int size = 1; size <= numOfAgents; size++)
150 numOfCoalitionsInSearchSpace += size
151 * Combinations.getNumOfCSOfCertainSize(numOfAgents, size);
152 return (numOfCoalitionsInSearchSpace);
153 }
154
155 // The following is an alternative approach that uses "BigInteger"
156 public static BigInteger getNumOfCoalitionsInSearchSpace_bitIntegerVersion(
157 int numOfAgents) {
158 BigInteger numOfCoalitionsInSearchSpace = BigInteger.valueOf(0);
159 for (int size = 1; size <= numOfAgents; size++) {
160 numOfCoalitionsInSearchSpace = numOfCoalitionsInSearchSpace
161 .add(Combinations.getNumOfCSOfCertainSize_bigIntegerVersion(
162 numOfAgents, size));
163 numOfCoalitionsInSearchSpace = numOfCoalitionsInSearchSpace
164 .multiply(BigInteger.valueOf(size));
165 }
166 return (numOfCoalitionsInSearchSpace);
167 }
168
169 // ******************************************************************************************************
170
171 /**
172 * Compute the number of possible coalition structures of a particular size.
173 */
174 public static long getNumOfCSOfCertainSize(int numOfAgents, int size) {
175 if ((size == 1) || (size == numOfAgents))
176 return (1);
177 else
178 return (size * getNumOfCSOfCertainSize(numOfAgents - 1, size)
179 + getNumOfCSOfCertainSize(numOfAgents - 1, size - 1));
180 }
181
182 // The following is an alternative approach that uses "BigInteger"
183 public static BigInteger getNumOfCSOfCertainSize_bigIntegerVersion(
184 int numOfAgents, int size) {
185 if ((size == 1) || (size == numOfAgents))
186 return (BigInteger.valueOf(1));
187 else {
188 BigInteger solution = getNumOfCSOfCertainSize_bigIntegerVersion(
189 numOfAgents - 1, size).multiply(BigInteger.valueOf(size));
190 solution = solution.add(getNumOfCSOfCertainSize_bigIntegerVersion(
191 numOfAgents - 1, size - 1));
192 return (solution);
193 }
194 }
195
196 // ******************************************************************************************************
197
198 /**
199 * Convert a combination (a coalition) from int format to bit format
200 */
201 public static int convertCombinationFromByteToBitFormat(
202 int[] combinationInByteFormat) {
203 return (convertCombinationFromByteToBitFormat(combinationInByteFormat,
204 combinationInByteFormat.length));
205 }
206
207 public static int convertCombinationFromByteToBitFormat(
208 int[] combinationInByteFormat, int combinationSize) {
209 int combinationInBitFormat = 0;
210 for (int i = 0; i < combinationSize; i++)
211 // Add agent "combinationInByteFormat[i]" to
212 // "combinationInBitFormat"
213 combinationInBitFormat += 1 << (combinationInByteFormat[i] - 1);
214
215 return (combinationInBitFormat);
216 }
217
218 // ******************************************************************************************************
219
220 /**
221 * Convert a combination from bit format to int format (e.g. given 4 agents,
222 * 0110 becomes {2,3})
223 */
224 public static int[] convertCombinationFromBitToByteFormat(
225 int combinationInBitFormat, int numOfAgents, int combinationSize) {
226 int[] combinationInByteFormat = new int[combinationSize];
227 int j = 0;
228 for (int i = 0; i < numOfAgents; i++) {
229 if ((combinationInBitFormat & (1 << i)) != 0) { // if agent "i+1" is
230 // a member of
231 // "combinationInBitFormat"
232 combinationInByteFormat[j] = i + 1;
233 j++;
234 }
235 }
236 return (combinationInByteFormat);
237 }
238
239 // ******************************************************************************************************
240
241 /**
242 * Convert a combination from bit format to int format (e.g. given 4 agents,
243 * 0110 becomes {2,3})
244 */
245 public static int[] convertCombinationFromBitToByteFormat(
246 int combinationInBitFormat, int numOfAgents) {
247 // compute the size of the combination
248 int combinationSize = getSizeOfCombinationInBitFormat(
249 combinationInBitFormat, numOfAgents);
250 return (convertCombinationFromBitToByteFormat(combinationInBitFormat,
251 numOfAgents, combinationSize));
252 }
253
254 // ******************************************************************************************************
255
256 /**
257 * Convert a set of combination (a coalition structure) from bit format to
258 * int format
259 */
260 public static int[][] convertSetOfCombinationsFromBitToByteFormat(
261 int[] setOfCombinationsInBitFormat, int numOfAgents) {
262 // Initialization
263 int[] sizeOfEachCombination = new int[setOfCombinationsInBitFormat.length];
264 for (int i = setOfCombinationsInBitFormat.length - 1; i >= 0; i--)
265 sizeOfEachCombination[i] = getSizeOfCombinationInBitFormat(
266 setOfCombinationsInBitFormat[i], numOfAgents);
267
268 return (convertSetOfCombinationsFromBitToByteFormat(
269 setOfCombinationsInBitFormat, numOfAgents,
270 sizeOfEachCombination));
271 }
272
273 // ******************************************************************************************************
274
275 /**
276 * Convert a set of combination (a coalition structure) from bit to int
277 * format, where the length of each coalition is provided in the array
278 * "lengthOfEachCoalition" (i.e., coalition "CS[i]" is of size
279 * "lengthOfEachCoalition[i]").
280 */
281 public static int[][] convertSetOfCombinationsFromBitToByteFormat(
282 int[] setOfCombinationsInBitFormat, int numOfAgents,
283 int[] sizeOfEachCombination) {
284 int[][] setOfCombinationsInByteFormat = new int[setOfCombinationsInBitFormat.length][];
285 for (int i = 0; i < setOfCombinationsInBitFormat.length; i++)
286 setOfCombinationsInByteFormat[i] = convertCombinationFromBitToByteFormat(
287 setOfCombinationsInBitFormat[i], numOfAgents);
288
289 return (setOfCombinationsInByteFormat);
290 }
291
292 // ******************************************************************************************************
293
294 /**
295 * Convert a set of combination (a coalition structure) from int to bit
296 * format
297 */
298 public static int[] convertSetOfCombinationsFromByteToBitFormat(
299 int[][] setOfCombinationsInByteFormat) {
300 int[] setOfCombinationsInBitFormat = new int[setOfCombinationsInByteFormat.length];
301 for (int i = 0; i < setOfCombinationsInByteFormat.length; i++)
302 setOfCombinationsInBitFormat[i] = convertCombinationFromByteToBitFormat(
303 setOfCombinationsInByteFormat[i]);
304 return (setOfCombinationsInBitFormat);
305 }
306
307 // ******************************************************************************************************
308
309 /**
310 * - This method returns the list of possible combinations of a set of size
311 * = "size". - Here, a coalition is represented using ints (i.e., each agent
312 * is represented using a int)
313 */
314 public static int[][] getCombinationsOfGivenSize(int numOfAgents, int size)
315 /*
316 * Here, we start by generating the combination: "1,2,...,size" which is the
317 * last combination in the list. Then, from the current combination, we find
318 * the combination that is located before it, and so on until we reach the
319 * first combination in the list, which is:
320 * "numOfAgents-(size-1), numOfAgents-(size-2), ..., numOfAgents"
321 */
322 {
323 int[][] list = new int[(int) binomialCoefficient(numOfAgents,
324 size)][size];
325 int index = list.length - 1;
326
327 // Generate the combination: "1,2,...,size"
328 for (int i = 1; i <= size; i++)
329 list[index][i - 1] = i;
330
331 // Generate the remaining combinations
332 int maxPossibleValueForFirstAgent = numOfAgents - size + 1;
333 while (index > 0) {
334 for (int i = size - 1; i >= 0; i--) {
335 // If the agent at index "i" is smaller than the largest
336 // possible agent that can be at index "i"
337 if (list[index][i] < maxPossibleValueForFirstAgent + i) {
338 index--;
339
340 for (int j = 0; j < i; j++)
341 list[index][j] = list[index + 1][j];
342
343 list[index][i] = list[index + 1][i] + 1;
344
345 for (int j = i + 1; j < size; j++)
346 list[index][j] = list[index][j - 1] + 1;
347
348 break;
349 }
350 }
351 }
352 return (list);
353 }
354
355 // ******************************************************************************************************
356
357 /**
358 * - This method returns the list of possible combinations of a set of size
359 * = "size". - Here, a coalition is represented using bits (i.e., each agent
360 * is represented using a bit)
361 */
362 public static int[] getCombinationsOfGivenSizeInBitFormat(int numOfAgents,
363 int size)
364 /*
365 * Here, we start by generating the combination: "1,2,...,size" which is the
366 * LAST combination in the list. Then, from the current combination, we find
367 * the combination that is located BEFORE it, and so on until we reach the
368 * first combination in the list, which is:
369 * "numOfAgents-(size-1), numOfAgents-(size-2), ..., numOfAgents"
370 */
371 {
372 // set "onesBeforeIndex" such that it contains 1,1,1,1... "k" times, and
373 // then contains zeros
374 final int[] onesBeforeIndex = new int[numOfAgents + 1];
375 for (int k = numOfAgents; k > 0; k--)
376 onesBeforeIndex[k] = (1 << k) - 1;
377
378 int[] list = new int[(int) binomialCoefficient(numOfAgents, size)];
379 int index = list.length - 1;
380
381 // Generate the combination: "1,2,...,size"
382 list[index] = 0;
383 for (int i = 1; i <= size; i++)
384 list[index] += (1 << (i - 1)); // add agent "i" to the coalition
385 // "list[index]"
386
387 // Generate the remaining combinations
388 int maxPossibleValueForFirstAgent = numOfAgents - size + 1;
389 while (index > 0) // For every coalition in the list
390 {
391 // Initializing the index of the agent that we are trying to
392 // identify. Here, "size-1"
393 int i = size - 1; // means that we trying to identify the last agent
394 // in the coalition.
395
396 for (int k = numOfAgents; k > 0; k--) {
397 if ((list[index] & (1 << (k - 1))) != 0) // If agent "k" is in
398 // the coalition
399 // "list[index]"
400 {
401 if (k < maxPossibleValueForFirstAgent + i) // If agent "k"
402 // is smaller
403 // than the
404 // largest
405 // possible
406 // agent that
407 // can be at
408 // index "i"
409 {
410 index--;
411
412 list[index] = (list[index + 1]
413 & onesBeforeIndex[k - 1]);
414
415 list[index] += (1 << k); // add agent "k+1" to the
416 // coalition "list[index]"
417
418 for (int j = 1; j < size - i; j++)
419 list[index] += (1 << (k + j)); // add agent
420 // "(k+j)+1" to the
421 // coalition
422 // "list[index]"
423
424 i--;
425 break;
426 }
427 i--;
428 }
429 }
430 }
431 return (list);
432 }
433
434 // *********************************************************************************************************
435
436 /**
437 * Given a coalition in a list of coalitions that is ordered as in DCVD,
438 * this method sets this coalition to be the coalition located before it.
439 * HERE, THE COMBINATION IS GIVEN IN BYTE FORMAT
440 */
441 public static void getPreviousCombination(final int numOfAgents,
442 final int size, int[] combination) {
443 /*
444 * maxPossibleValueForFirstAgent: is the maximum value that the first
445 * agent in the coalition can have. For example, if we have coalitions
446 * of size 3 out of 9 agents, then, since each combination is ordered in
447 * an ascending order, the first agent cannot be greater than 7, and
448 * that is in combination: (7,8,9)
449 */
450 final int maxPossibleValueForFirstAgent = numOfAgents - size + 1;
451 for (int i = size - 1; i >= 0; i--) {
452 if (combination[i] < maxPossibleValueForFirstAgent + i) {
453 combination[i]++;
454 for (int j = i + 1; j < size; j++) {
455 combination[j] = combination[j - 1] + 1;
456 }
457 break;
458 }
459 }
460 }
461
462 // ************************************************************************************************
463
464 /**
465 * get all the possible subsets of a multiset
466 */
467 public static int[][] getCombinationsOfGivenSize_multisetVersion_oldVersion(
468 int[] multiset) {
469 // initialization
470 int[][] subsets;
471 int indexInSubsets = 0;
472 int[] underlyingSet = General.getUnderlyingSet(multiset);
473 int sizeOfUnderlyingSet = underlyingSet.length;
474
475 // Compute the multiplicity of each member
476 int[] multiplicity = new int[sizeOfUnderlyingSet];
477 for (int i = 0; i < sizeOfUnderlyingSet; i++)
478 multiplicity[i] = General.getMultiplicity(underlyingSet[i],
479 multiset);
480
481 // compute an upper bound on the number of possible subsets of the
482 // multiset
483 int[] sortedMultiplicity = General.sortArray(multiplicity, false);
484 int upperBoundOnNumOfSubsets = 0;
485 for (int curSize = 1; curSize <= sizeOfUnderlyingSet; curSize++) {
486 int x = 1;
487 for (int i = 0; i < curSize; i++)
488 x *= sortedMultiplicity[i];
489 upperBoundOnNumOfSubsets += x * Combinations
490 .binomialCoefficient(sizeOfUnderlyingSet, curSize);
491 }
492 // Allocate memory for "subspaces"
493 subsets = new int[upperBoundOnNumOfSubsets][];
494
495 // Generate the possible combinations of { 1, 2, ..., sizeOfUnderlyinSet
496 // }
497 for (int sizeOfCombination = 1; sizeOfCombination <= sizeOfUnderlyingSet; sizeOfCombination++) {
498 int[] curCombination = new int[sizeOfCombination];
499 long numOfCombinationsOfCurSize = Combinations.binomialCoefficient(
500 sizeOfUnderlyingSet, sizeOfCombination);
501 for (int i = 0; i < numOfCombinationsOfCurSize; i++) {
502 if (i == 0)
503 curCombination = Combinations.getCombinationAtGivenIndex(
504 sizeOfCombination, 0, sizeOfUnderlyingSet);
505 else
506 Combinations.getNextCombination(sizeOfUnderlyingSet,
507 sizeOfCombination, curCombination);
508
509 // for the current combination of { 1, 2, ...,
510 // sizeOfUnderlyingSet }: replace "i"
511 // with X instances of the i^{th} element of the underlying set,
512 // where X=1, and then
513 // X=2, and then X=3, and so on, until X equals the multiplicity
514 // of the i^{th} element
515 indexInSubsets += getSubsetsThatMatchCombination(curCombination,
516 sizeOfCombination, subsets, indexInSubsets,
517 underlyingSet, multiplicity);
518 }
519 }
520 // rescale "subsets" such that its size equals the number of subsets in
521 // it
522 int[][] temp = new int[indexInSubsets][];
523 for (int i = 0; i < indexInSubsets; i++)
524 temp[i] = subsets[i];
525 subsets = temp;
526
527 return (subsets);
528 }
529
530 // ************************************************************************************************
531
532 /**
533 * This is only called in method:
534 * "getCombinationsOfGivenSize_multisetVersion_oldVersion"
535 *
536 * for the current combination of { 1, 2, ..., sizeOfUnderlyingSet }:
537 * replace "i" with X instances of the i^{th} element of the underlying set,
538 * where X=1, and then X=2, and then X=3, and so on, until X equals the
539 * multiplicity of the i^{th} element
540 *
541 * Add each of the resulting subsets to "subsets".
542 */
543 private static int getSubsetsThatMatchCombination(int[] combination,
544 int sizeOfCombination, int[][] subsets, int indexInSubsets,
545 int[] underlyingSet, int[] multiplicity) {
546 /*
547 * In this method, we will use "numOfInstances", which explained in the
548 * following example: if numOfInstances = [2,3,5], this this means the
549 * number of times we need to repeat the first element of the underlying
550 * set is 2, and the number of times we need to repeat the second
551 * element is 3, and so on.
552 */
553
554 // Initialization
555 int[] numOfRepetitions = new int[sizeOfCombination];
556
557 // Compute the number of possible combinations of the numbers of
558 // repetition
559 int numOfPossibilitiesOfNumOfRepetitions = 1;
560 for (int i = 0; i < combination.length; i++)
561 numOfPossibilitiesOfNumOfRepetitions *= multiplicity[combination[i]
562 - 1];
563
564 // For each of the remaining possiblities of the numbers of combinations
565 for (int i = 0; i < numOfPossibilitiesOfNumOfRepetitions; i++) {
566 if (i == 0) {
567 // Initializing the numbers of repetition to 1,1,...,1
568 for (int j = 0; j < sizeOfCombination; j++)
569 numOfRepetitions[j] = 1;
570 } else {
571 // get the next numbers of repetition (e.g., if the numbers
572 // where: 2,2,4, and the
573 // multiplicities were: 3,3,4, then the next numbers of
574 // repetitions would be 2,3,1
575 for (int j = sizeOfCombination - 1; j >= 0; j--) {
576 if (numOfRepetitions[j] < multiplicity[combination[j]
577 - 1]) {
578 numOfRepetitions[j] += 1;
579 for (int k = j + 1; k < sizeOfCombination; k++)
580 numOfRepetitions[k] = 1;
581 break;
582 }
583 }
584 }
585 // Compute the size of the current subset (based on the numbers of
586 // repetitions)
587 int sizeOfCurSubset = 0;
588 for (int j = 0; j < sizeOfCombination; j++)
589 sizeOfCurSubset += numOfRepetitions[j];
590 subsets[indexInSubsets] = new int[sizeOfCurSubset];
591
592 // Set the current subset based on the current combination and
593 // numbers of repetition
594 int m = 0;
595 for (int j = 0; j < sizeOfCombination; j++) {
596 for (int k = 0; k < numOfRepetitions[j]; k++) {
597 subsets[indexInSubsets][m] = underlyingSet[combination[j]
598 - 1];
599 m++;
600 }
601 }
602 // Update the index in the list of subsets
603 indexInSubsets++;
604 }
605 // return the number of subsets that were generated in this method
606 return (numOfPossibilitiesOfNumOfRepetitions);
607 }
608
609 // ******************************************************************************************************
610
611 /**
612 * Given a coalition in a list of coalitions that is ordered as in DCVD,
613 * this method sets this coalition to be the coalition located before it.
614 * HERE, THE COMBINATION IS GIVEN IN BIT FORMAT
615 */
616 public static int getPreviousCombinationInBitFormat(final int numOfAgents,
617 final int size, int combination) {
618 // Initializing the index of the agent that we are trying to identify.
619 // Here, "size-1"
620 int i = size - 1; // means that we trying to identify the last agent in
621 // the coalition.
622
623 /*
624 * maxPossibleValueForFirstAgent: is the maximum value that the first
625 * agent in the coalition can have. For example, if we have coalitions
626 * of size 3 out of 9 agents, then, since each combination is ordered in
627 * an ascending order, the first agent cannot be greater than 7, and
628 * that is in combination: (7,8,9)
629 */
630 int maxPossibleValueForFirstAgent = numOfAgents - size + 1;
631 for (int k = numOfAgents; k > 0; k--) {
632 if ((combination & (1 << (k - 1))) != 0) // If agent "k" is in
633 // "combination"
634 {
635 if (k < maxPossibleValueForFirstAgent + i) // If agent "k" is
636 // smaller than the
637 // largest possible
638 // agent that can be
639 // at index "i"
640 {
641 combination &= (1 << (k - 1)) - 1; // copy the part in
642 // "combination" that is
643 // before "k", and set the remaining part to zeros
644
645 combination += (1 << k); // to replace agent "k" with agent
646 // "k+1"
647
648 for (int j = 1; j < size - i; j++) // set the remaining
649 // agents
650 combination += (1 << (k + j)); // add agent "(k+j)+1" to
651 // "combination"
652
653 i--;
654 break;
655 }
656 i--;
657 }
658 }
659 return (combination);
660 }
661
662 // *********************************************************************************************************
663
664 /**
665 * Given a coalition in a list of coalitions that is ordered as in DCVD,
666 * this method sets this coalition to be the coalition located after it.
667 * HERE, THE COMBINATION IS REPRESENTED IN BYTE FORMAT.
668 */
669 public static void getNextCombination(int numOfAgents, int size,
670 int[] combination) {
671 /*
672 * maxPossibleValueForFirstAgent: is the maximum value that the first
673 * agent in the coalition can have. For example, if we have coalitions
674 * of size 3 out of 9 agents, then, since each combination is ordered in
675 * an ascending order, the first agent cannot be greater than 7, and
676 * that is in combination: (7,8,9)
677 */
678 final int maxPossibleValueForFirstAgent = numOfAgents - size + 1;
679 for (int i = size - 1; i > 0; i--) {
680 if (combination[i] != combination[i - 1] + 1) {
681 combination[i]--;
682 for (int j = i + 1; j < size; j++) {
683 combination[j] = maxPossibleValueForFirstAgent + j;
684 }
685 return;
686 }
687 }
688 // If we reach this instruction, it means that we reached a special case
689 combination[0]--;
690 for (int j = 1; j < size; j++) {
691 combination[j] = maxPossibleValueForFirstAgent + j;
692 }
693 }
694
695 // ******************************************************************************************************
696
697 /**
698 * More efficient, but not lexicographic order. I got it from the very end
699 * of:
700 * http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
701 */
702 public static int getPreviousCombinationInBitFormat2(int numOfAgents,
703 int size, int combination) {
704 int t = (combination | (combination - 1)) + 1;
705 return (t | ((((t & -t) / (combination & -combination)) >> 1) - 1));
706
707 // A DIFFERENT VERSION, SAME EFFICIENCY IT SEEMS
708
709 // int t = combination | (combination - 1);
710 // return( (t + 1) | (((~t & -~t) - 1) >>
711 // (Integer.numberOfTrailingZeros(combination) + 1)) );
712 }
713
714 // ******************************************************************************************************
715
716 /**
717 * Given a coalition in a list of coalitions that is ordered as in DCVD,
718 * this method sets this coalition to be the coalition located after it.
719 * HERE, THE COMBINATION IS REPRESENTED IN BIT FORMAT.
720 */
721 public static int getNextCombinationInBitFormat(int numOfAgents, int size,
722 int combination) {
723 int k2 = 0;
724
725 // Initializing the index of the agent that we are trying to identify.
726 // Here, "size-1"
727 int i = size - 1; // means that we trying to identify the last agent in
728 // the coalition.
729
730 /*
731 * maxPossibleValueForFirstAgent: is the maximum value that the first
732 * agent in the coalition can have. For example, if we have coalitions
733 * of size 3 out of 9 agents, then, since each combination is ordered in
734 * an ascending order, the first agent cannot be greater than 7, and
735 * that is in combination: (7,8,9)
736 */
737 final int maxPossibleValueForFirstAgent = numOfAgents - size + 1;
738 for (int k = numOfAgents; k > 0; k--) {
739 if ((combination & (1 << (k - 1))) != 0) // If agent "k" is in the
740 // coalition
741 {
742 if ((combination & (1 << (k - 2))) == 0) // If agent "k-1" is
743 // not in the
744 // coalition
745 {
746 combination &= (1 << (k - 1)) - 1; // copy the part in
747 // "combination" that is
748 // before "k", and set the remaining part to zeros
749
750 combination += (1 << (k - 2)); // This way, we replace agent
751 // "k" with "k-1"
752
753 for (int j = i + 1; j < size; j++) // set the remaining
754 // agents
755 combination += (1 << (maxPossibleValueForFirstAgent + j
756 - 1));
757
758 return (combination);
759 }
760 i--;
761 if (i == 0) {
762 // Store the first agent in the coalition
763 k2 = k - 1;
764 while ((combination & (1 << (k2 - 1))) == 0) { // while
765 // agent
766 // "k2" is
767 // not in
768 // "combination"
769 k2--;
770 }
771 break;
772 }
773 }
774 }
775 // If we reach this instruction, it means that we reached a special case
776 combination = (1 << (k2 - 2)); // Initialize the coalition to contain
777 // only agent "k2-1"
778 for (int j = 1; j < size; j++)
779 // Add agent "(maxPossibleValueForFirstAgent+j)" to "combination"
780 combination += (1 << (maxPossibleValueForFirstAgent + j) - 1);
781
782 return (combination);
783 }
784
785 // ******************************************************************************************************
786
787 /**
788 * This method generates the coalitions located at the given index (assuming
789 * that the coalitions are order as in DCVC).
790 *
791 * IMPORTANT EXAMPLE: We have 10 possible coalitions of size 3 out of 5
792 * agents. Now if index=0, then this method would return "3,4,5", and if
793 * index=9, the method would return "1,2,3"
794 */
795 public static int[] getCombinationAtGivenIndex(int size, int index,
796 int numOfAgents) {
797 // Initialization
798 index++;
799 initPascalMatrix(numOfAgents + 1, numOfAgents + 1);
800 int[] M = new int[size];
801 boolean done = false;
802
803 /* 1 */ int j = 1;
804 int s1 = size;
805 do {
806 // Check the values: PascalMatrix[s1,1],PascalMatrix[s1,2],...
807 /* 2 */ int x = 1;
808 while (pascalMatrix[s1 - 1][x - 1] < index)
809 x++;
810
811 /* 3 */ M[j - 1] = (numOfAgents - s1 + 1) - x + 1;
812
813 /* 4 */ if (pascalMatrix[s1 - 1][x - 1] == index) {
814 // Set the rest of the coalition as follows:
815 for (int k = j; k <= size - 1; k++)
816 M[k] = M[k - 1] + 1;
817 done = true;
818 } else // Otherwise
819 {
820 j++;
821 index -= pascalMatrix[s1 - 1][x - 2];
822 s1--;
823 }
824 } while (done == false);
825 return (M);
826 }
827
828 // *********************************************************************************************************
829
830 /**
831 * Given a coalition C : |C|=s, this method returns the index of C in the
832 * list of coalitions of size s IMPORTANT EXAMPLE: We have 10 possible
833 * coalitions of size 3 out of 5 agents. Now if the coalition is "3,4,5",
834 * then this method would return 0, and if the coalition is "1,2,3", the
835 * method returns 9.
836 */
837 public static int getIndexOfCombination(final int[] combination,
838 final int size, final int numOfAgents) {
839 long indexOfCombination = 0;
840 if (size == 1)
841 indexOfCombination = numOfAgents - combination[0] + 1;
842 else {
843 boolean sequence = true;
844 for (int i1 = size - 1; i1 >= 1; i1--) {
845 if (combination[i1] - combination[i1 - 1] > 1) {
846 indexOfCombination = pascalMatrix[size - i1
847 - 1][(numOfAgents - size + i1) - combination[i1]
848 + 1];
849 for (int i2 = i1 - 1; i2 >= 0; i2--) {
850 indexOfCombination += pascalMatrix[size - i2
851 - 1][(numOfAgents - size + i2)
852 - combination[i2]];
853 }
854 sequence = false;
855 break;
856 }
857 }
858 if (sequence)
859 indexOfCombination = pascalMatrix[size - 1][numOfAgents - size
860 - combination[0] + 1];
861 }
862 return (((int) indexOfCombination) - 1);
863 }
864}
Note: See TracBrowser for help on using the repository browser.