[40] | 1 | package geniusweb.ip.general;
|
---|
| 2 |
|
---|
| 3 | import 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 | */
|
---|
| 12 | public 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 | } |
---|