001// ============================================================================ 002// Copyright 2006-2012 Daniel W. Dyer 003// 004// Licensed under the Apache License, Version 2.0 (the "License"); 005// you may not use this file except in compliance with the License. 006// You may obtain a copy of the License at 007// 008// http://www.apache.org/licenses/LICENSE-2.0 009// 010// Unless required by applicable law or agreed to in writing, software 011// distributed under the License is distributed on an "AS IS" BASIS, 012// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013// See the License for the specific language governing permissions and 014// limitations under the License. 015// ============================================================================ 016package squidpony.squidmath; 017 018import java.io.Serializable; 019import java.math.BigInteger; 020import java.util.ArrayList; 021import java.util.Collection; 022import java.util.Collections; 023import java.util.Iterator; 024import java.util.List; 025 026/** 027 * Permutation generator for generating all permutations for all sets up to 028 * 20 elements in size. While 20 may seem a low limit, bear in mind that 029 * the number of permutations of a set of size n is n! For a set of 21 030 * items, the number of permutations is bigger than can be stored in Java's 031 * 64-bit long integer data type. Therefore it seems unlikely that you 032 * could ever generate, let alone process, all of the permutations in a 033 * reasonable time frame. For this reason the implementation is optimised for 034 * sets of size 20 or less (this affords better performance by allowing primitive 035 * numeric types to be used for calculations rather than 036 * {@link java.math.BigInteger}). 037 * <br> 038 * Originally part of the <a href="http://maths.uncommons.org/">Uncommon Maths software package</a>. 039 * @param <T> The type of element that the permutation will consist of. 040 * @author Daniel Dyer (modified from the original version written by Michael 041 * Gilleland of Merriam Park Software - 042 * <a href="http://www.merriampark.com/perm.htm">http://www.merriampark.com/perm.htm</a>). 043 * @see CombinationGenerator 044 */ 045public class PermutationGenerator<T> implements Iterable<List<T>>, Serializable 046{ 047 private static final long serialVersionUID = 514276118639629743L; 048 049 private final T[] elements; 050 private final int[] permutationIndices; 051 private long remainingPermutations; 052 private long totalPermutations; 053 054 055 /** 056 * Permutation generator that generates all possible orderings of 057 * the elements in the specified set. 058 * @param elements The elements to permute; will be modified, so this should be copied beforehand 059 */ 060 public PermutationGenerator(T[] elements) 061 { 062 if (elements.length > 20) 063 { 064 throw new IllegalArgumentException("Size must be less than or equal to 20."); 065 } 066 this.elements = elements; 067 permutationIndices = new int[elements.length]; 068 totalPermutations = MathExtras.factorial(elements.length); 069 reset(); 070 } 071 072 073 /** 074 * Permutation generator that generates all possible orderings of 075 * the elements in the specified set. 076 * @param elements The elements to permute. 077 * @param filler An array of T with the same length as elements or less (often 0); 078 * needed because GWT can't create a generic array. If elements is not 079 * a Collection defined in the JDK (by GWT), then this should have 080 * exactly the same length as elements, since GWT can create larger 081 * versions of an array on its own, but our code can't easily. 082 */ 083 public PermutationGenerator(Collection<T> elements, T[] filler) 084 { 085 this(elements.toArray(filler)); 086 } 087 088 089 /** 090 * Resets the generator state. 091 */ 092 public final void reset() 093 { 094 for (int i = 0; i < permutationIndices.length; i++) 095 { 096 permutationIndices[i] = i; 097 } 098 remainingPermutations = totalPermutations; 099 } 100 101 102 /** 103 * Returns the number of permutations not yet generated. 104 * @return The number of unique permutations still to be generated. 105 */ 106 public long getRemainingPermutations() 107 { 108 return remainingPermutations; 109 } 110 111 112 /** 113 * Returns the total number of unique permutations that can be 114 * generated for the given set of elements. 115 * @return The total number of permutations. 116 */ 117 public long getTotalPermutations() 118 { 119 return totalPermutations; 120 } 121 122 /** 123 * Returns the total number of unique permutations that can be 124 * generated for the given count of permute-able elements. 125 * Typically used with the static methods of this class that 126 * find permutation indices. 127 * @param count the number of elements (typically indices) you want to find a permutation of 128 * @return The total number of permutations. 129 */ 130 public static long getTotalPermutations(int count) 131 { 132 return MathExtras.factorial(count); 133 } 134 135 136 /** 137 * Returns the total number of unique permutations that can be 138 * generated for the given count of permute-able elements. 139 * Typically used with the static methods of this class that 140 * find permutation indices and involve BigInteger values. 141 * @param count the number of elements (typically indices) you want to find a permutation of 142 * @return The total number of permutations. 143 */ 144 public static BigInteger getBigTotalPermutations(int count) 145 { 146 return MathExtras.bigFactorial(count); 147 } 148 149 150 /** 151 * Are there more permutations that have not yet been returned? 152 * @return true if there are more permutations, false otherwise. 153 */ 154 public boolean hasMore() 155 { 156 return remainingPermutations > 0; 157 } 158 159 160 /** 161 * Generate the next permutation and return an array containing 162 * the elements in the appropriate order. This overloaded method 163 * allows the caller to provide an array that will be used and returned. 164 * The purpose of this is to improve performance when iterating over 165 * permutations. This method allows a single array instance to be reused. 166 * @param destination Provides an array to use to create the 167 * permutation. The specified array must be the same length as a 168 * permutation. This is the array that will be returned, once 169 * it has been filled with the elements in the appropriate order. 170 * @return The next permutation as an array. 171 */ 172 public T[] nextPermutationAsArray(T[] destination) 173 { 174 if (destination.length != elements.length) 175 { 176 throw new IllegalArgumentException("Destination array must be the same length as permutations."); 177 } 178 generateNextPermutationIndices(); 179 // Generate actual permutation. 180 for (int i = 0; i < permutationIndices.length; i++) 181 { 182 destination[i] = elements[permutationIndices[i]]; 183 } 184 return destination; 185 } 186 187 188 /** 189 * Generate the next permutation and return a list containing 190 * the elements in the appropriate order. 191 * @see #nextPermutationAsList(List) 192 * @return The next permutation as a list. 193 */ 194 public List<T> nextPermutationAsList() 195 { 196 List<T> permutation = new ArrayList<T>(elements.length); 197 return nextPermutationAsList(permutation); 198 } 199 200 201 /** 202 * Generate the next permutation and return a list containing 203 * the elements in the appropriate order. This overloaded method 204 * allows the caller to provide a list that will be used and returned. 205 * The purpose of this is to improve performance when iterating over 206 * permutations. If the {@link #nextPermutationAsList()} method is 207 * used it will create a new list every time. When iterating over 208 * permutations this will result in lots of short-lived objects that 209 * have to be garbage collected. This method allows a single list 210 * instance to be reused in such circumstances. 211 * @param destination Provides a list to use to create the 212 * permutation. This is the list that will be returned, once 213 * it has been filled with the elements in the appropriate order. 214 * @return The next permutation as a list. 215 */ 216 public List<T> nextPermutationAsList(List<T> destination) 217 { 218 generateNextPermutationIndices(); 219 // Generate actual permutation. 220 destination.clear(); 221 for (int i : permutationIndices) 222 { 223 destination.add(elements[i]); 224 } 225 return destination; 226 } 227 228 /** 229 * Generate the indices into the elements array for the next permutation. The 230 * algorithm is from Kenneth H. Rosen, Discrete Mathematics and its Applications, 231 * 2nd edition (NY: McGraw-Hill, 1991), p. 284) 232 */ 233 private void generateNextPermutationIndices() 234 { 235 if (remainingPermutations == 0) 236 { 237 throw new IllegalStateException("There are no permutations remaining. " + 238 "Generator must be reset to continue using."); 239 } 240 else if (remainingPermutations < totalPermutations) 241 { 242 // Find largest index j with permutationIndices[j] < permutationIndices[j + 1] 243 int j = permutationIndices.length - 2; 244 while (permutationIndices[j] > permutationIndices[j + 1]) 245 { 246 j--; 247 } 248 249 // Find index k such that permutationIndices[k] is smallest integer greater than 250 // permutationIndices[j] to the right of permutationIndices[j]. 251 int k = permutationIndices.length - 1; 252 while (permutationIndices[j] > permutationIndices[k]) 253 { 254 k--; 255 } 256 257 // Interchange permutation indices. 258 int temp = permutationIndices[k]; 259 permutationIndices[k] = permutationIndices[j]; 260 permutationIndices[j] = temp; 261 262 // Put tail end of permutation after jth position in increasing order. 263 int r = permutationIndices.length - 1; 264 int s = j + 1; 265 266 while (r > s) 267 { 268 temp = permutationIndices[s]; 269 permutationIndices[s] = permutationIndices[r]; 270 permutationIndices[r] = temp; 271 r--; 272 s++; 273 } 274 } 275 --remainingPermutations; 276 } 277 278 private int[] getPermutationShift(T[] perm) { 279 int[] sh = new int[perm.length]; 280 boolean[] taken = new boolean[perm.length]; 281 282 for (int i = 0; i < perm.length - 1; i++) { 283 int ctr = -1; 284 for (int j = 0; j < perm.length; j++) { 285 if (!taken[j]) 286 ctr++; 287 if (perm[j] == elements[i]) { 288 taken[j] = true; 289 sh[i] = ctr; 290 break; 291 } 292 } 293 } 294 return sh; 295 } 296 297 private int[] getPermutationShift(List<T> perm) { 298 int length = perm.size(); 299 int[] sh = new int[length]; 300 boolean[] taken = new boolean[length]; 301 302 for (int i = 0; i < length - 1; i++) { 303 int ctr = -1; 304 for (int j = 0; j < length; j++) { 305 if (!taken[j]) 306 ctr++; 307 if (perm.get(j) == elements[i]) { 308 taken[j] = true; 309 sh[i] = ctr; 310 break; 311 } 312 } 313 } 314 return sh; 315 } 316 317 /** 318 * Given an array of T that constitutes a permutation of the elements this was constructed with, finds the specific 319 * index of the permutation given a factoradic numbering scheme (not used by the rest of this class, except the 320 * decodePermutation() method). The index can be passed to decodePermutation to reproduce the permutation passed to 321 * this, or modified and then passed to decodePermutation(). Determines equality by identity, not by .equals(), so 322 * that equivalent values that have different references/identities can appear in the permuted elements. 323 * <br> 324 * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337 325 * @param perm an array of T that must be a valid permutation of this object's elements 326 * @return an encoded number that can be used to reconstruct the permutation when passed to decodePermutation() 327 */ 328 public long encodePermutation(T[] perm) 329 { 330 long e = 0; 331 if(perm == null || perm.length != elements.length) 332 return e; 333 int[] shift = getPermutationShift(perm); 334 for (int i = 1; i < shift.length; i++) { 335 e += shift[i] * MathExtras.factorialsStart[i]; 336 } 337 return e; 338 } 339 340 /** 341 * Given a List of T that constitutes a permutation of the elements this was constructed with, finds the specific 342 * index of the permutation given a factoradic numbering scheme (not used by the rest of this class, except the 343 * decodePermutation() method). The index can be passed to decodePermutation to reproduce the permutation passed to 344 * this, or modified and then passed to decodePermutation(). Determines equality by identity, not by .equals(), so 345 * that equivalent values that have different references/identities can appear in the permuted elements. 346 * <br> 347 * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337 348 * @param perm a List of T that must be a valid permutation of this object's elements 349 * @return an encoded number that can be used to reconstruct the permutation when passed to decodePermutation() 350 */ 351 public long encodePermutation(List<T> perm) 352 { 353 long e = 0; 354 if(perm == null || perm.size() != elements.length) 355 return e; 356 int[] shift = getPermutationShift(perm); 357 for (int i = 1; i < shift.length; i++) { 358 e += shift[i] * MathExtras.factorialsStart[i]; 359 } 360 return e; 361 } 362 363 private int[] factoradicDecode(long e) 364 { 365 int[] sequence = new int[elements.length]; 366 int base = 2; 367 368 for (int k = 1; k < elements.length; k++) 369 { 370 sequence[elements.length - 1 - k] = (int)(e % base); 371 e /= base; 372 373 base++; 374 } 375 return sequence; 376 } 377 378 /** 379 * Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access 380 * this) and an array of T with the same length as the elements this was constructed with, fills the array with the 381 * permutation described by the long as a special (factoradic) index into the possible permutations. You can get an 382 * index for a specific permutation with encodePermutation() or by generating a random number between 0 and 383 * getTotalPermutations(), if you want it randomly. 384 * <br> 385 * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337 386 * @param encoded the index encoded as a long 387 * @param destination an array of T that must have equivalent length to the elements this was constructed with 388 * @return the looked-up permutation, which is the same value destination will be assigned 389 */ 390 public T[] decodePermutation(long encoded, T[] destination) 391 { 392 if(destination == null) 393 return null; 394 encoded %= totalPermutations; 395 int[] sequence = factoradicDecode(encoded); 396 397 boolean[] set = new boolean[elements.length]; 398 399 for (int i = 0; i < elements.length; i++) 400 { 401 int s = sequence[i]; 402 int remainingPosition = 0; 403 int index; 404 405 // Find the s'th position in the permuted list that has not been set yet. 406 for (index = 0; index < elements.length; index++) 407 { 408 if (!set[index]) 409 { 410 if (remainingPosition == s) 411 break; 412 413 remainingPosition++; 414 } 415 } 416 417 destination[index] = elements[i]; 418 set[index] = true; 419 } 420 return destination; 421 } 422 423 /** 424 * Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access 425 * this), creates a List filled with the permutation described by the long as a special (factoradic) index into the 426 * possible permutations. You can get an index for a specific permutation with encodePermutation() or by generating a 427 * random number between 0 and getTotalPermutations(), if you want it randomly. 428 * <br> 429 * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337 430 * @param encoded the index encoded as a long 431 * @return a List of T that corresponds to the permutation at the encoded index 432 */ 433 public List<T> decodePermutation(long encoded) 434 { 435 ArrayList<T> list = new ArrayList<T>(elements.length); 436 Collections.addAll(list, elements); 437 return decodePermutation(encoded, list); 438 } 439 440 /** 441 * Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access 442 * this) and a List of T with the same length as the elements this was constructed with, fills the List with the 443 * permutation described by the long as a special (factoradic) index into the possible permutations. You can get an 444 * index for a specific permutation with encodePermutation() or by generating a random number between 0 and 445 * getTotalPermutations(), if you want it randomly. 446 * <br> 447 * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337 448 * @param encoded the index encoded as a long 449 * @param destination a List of T that must have equivalent size to the elements this was constructed with 450 * @return the looked-up permutation, which is the same value destination will be assigned 451 */ 452 public List<T> decodePermutation(long encoded, List<T> destination) 453 { 454 if(destination == null) 455 return null; 456 encoded %= totalPermutations; 457 int[] sequence = factoradicDecode(encoded); 458 459 boolean[] set = new boolean[elements.length]; 460 461 for (int i = 0; i < elements.length; i++) 462 { 463 int s = sequence[i]; 464 int remainingPosition = 0; 465 int index; 466 467 // Find the s'th position in the permuted list that has not been set yet. 468 for (index = 0; index < elements.length; index++) 469 { 470 if (!set[index]) 471 { 472 if (remainingPosition == s) 473 break; 474 475 remainingPosition++; 476 } 477 } 478 479 destination.set(index, elements[i]); 480 set[index] = true; 481 } 482 return destination; 483 } 484 /** 485 * <p>Provides a read-only iterator for iterating over the permutations 486 * generated by this object. This method is the implementation of the 487 * {@link Iterable} interface that permits instances of this class to be 488 * used with the new-style for loop.</p> 489 * <p>For example:</p> 490 * <pre> 491 * List<Integer> elements = Arrays.asList(1, 2, 3); 492 * PermutationGenerator<Integer> permutations = new PermutationGenerator(elements); 493 * for (List<Integer> p : permutations) 494 * { 495 * // Do something with each permutation. 496 * } 497 * </pre> 498 * @return An iterator. 499 * @since 1.1 500 */ 501 public Iterator<List<T>> iterator() 502 { 503 return new Iterator<List<T>>() 504 { 505 public boolean hasNext() 506 { 507 return hasMore(); 508 } 509 510 511 public List<T> next() 512 { 513 return nextPermutationAsList(); 514 } 515 516 517 public void remove() 518 { 519 throw new UnsupportedOperationException("Iterator does not support removal."); 520 } 521 }; 522 } 523 524 525 private static int[] getPermutationShift(int[] perm) { 526 int[] sh = new int[perm.length]; 527 boolean[] taken = new boolean[perm.length]; 528 529 for (int i = 0; i < perm.length - 1; i++) { 530 int ctr = -1; 531 for (int j = 0; j < perm.length; j++) { 532 if (!taken[j]) 533 ctr++; 534 if (perm[j] == i) { 535 taken[j] = true; 536 sh[i] = ctr; 537 break; 538 } 539 } 540 } 541 return sh; 542 } 543 /** 544 * Given an array of int that constitutes a permutation of indices, where no element in perm is repeated and all 545 * ints are less than perm.length, finds the specific index of the permutation given a factoradic numbering scheme 546 * (not used by the rest of this class, except the decodePermutation() method). The index can be passed to 547 * decodePermutation to reproduce the index permutation passed to this, or modified and then passed to 548 * decodePermutation(). 549 * <br> 550 * If perm is more than 20 items in length, you should use {@link #encodeBigPermutation} instead. 551 * <br> 552 * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337 553 * @param perm an array of int that is a permutation of the range from 0 (inclusive) to perm.length (exclusive, must be no more than 20) 554 * @return an encoded number that can be used to reconstruct the permutation when passed to decodePermutation() 555 */ 556 public static long encodePermutation(int[] perm) 557 { 558 long e = 0; 559 if(perm == null || perm.length <= 0) 560 return e; 561 int[] shift = getPermutationShift(perm); 562 for (int i = 1; i < shift.length; i++) { 563 e += shift[i] * MathExtras.factorialsStart[i]; 564 } 565 return e; 566 } 567 568 /** 569 * Given an array of int that constitutes a permutation of indices, where no element in perm is repeated and all 570 * ints are less than perm.length, finds the specific index of the permutation given a factoradic numbering scheme 571 * (not used by the rest of this class, except the decodePermutation() method). The index can be passed to 572 * decodePermutation to reproduce the index permutation passed to this, or modified and then passed to 573 * decodePermutation(). 574 * <br> 575 * If perm is 20 items or less in length, you can use {@link #encodePermutation} instead to get a 64-bit encoding. 576 * <br> 577 * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337 578 * @param perm an array of int that is a permutation of the range from 0 (inclusive) to perm.length (exclusive) 579 * @return an encoded number that can be used to reconstruct the permutation when passed to decodePermutation() 580 */ 581 public static BigInteger encodeBigPermutation(int[] perm) 582 { 583 BigInteger e = BigInteger.ZERO; 584 if(perm == null || perm.length <= 0) 585 return e; 586 int[] shift = getPermutationShift(perm); 587 for (int i = 1; i < shift.length; i++) { 588 e = e.add(MathExtras.bigFactorial(i).multiply(BigInteger.valueOf(shift[i]))); 589 } 590 return e; 591 } 592 593 594 private static int[] factoradicDecode(long e, int count) 595 { 596 int[] sequence = new int[count]; 597 int base = 2; 598 599 for (int k = 1; k < count; k++) 600 { 601 sequence[count - 1 - k] = (int)(e % base); 602 e /= base; 603 604 base++; 605 } 606 return sequence; 607 } 608 609 private static int[] factoradicDecode(BigInteger e, int count) 610 { 611 int[] sequence = new int[count]; 612 BigInteger base = BigInteger.valueOf(2); 613 614 for (int k = 1; k < count; k++) 615 { 616 sequence[count - 1 - k] = e.mod(base).intValue(); 617 e = e.divide(base); 618 619 base = base.add(BigInteger.ONE); 620 } 621 return sequence; 622 } 623 624 /** 625 * Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access 626 * this) and an int count of how many indices to find a permutation of, returns an array with the permutation 627 * of the indices described by the long as a special (factoradic) index into the possible permutations. You can get 628 * an index for a specific permutation with encodePermutation() or by generating a random number between 0 and 629 * getTotalPermutations(), if you want it randomly. 630 * <br> 631 * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337 632 * @param encoded the index encoded as a long 633 * @param count an int between 1 and 20, inclusive, that will be the size of the returned array 634 * @return the looked-up permutation as an int array with length equal to count 635 */ 636 public static int[] decodePermutation(long encoded, int count) 637 { 638 if(count <= 0) 639 return new int[0]; 640 encoded %= MathExtras.factorial(count); 641 int[] sequence = factoradicDecode(encoded, count), destination = new int[count]; 642 //char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' }; //change for elements 643 644 //char[] permuted = new char[n]; //change for destination 645 boolean[] set = new boolean[count]; 646 647 for (int i = 0; i < count; i++) 648 { 649 int s = sequence[i]; 650 int remainingPosition = 0; 651 int index; 652 653 // Find the s'th position in the permuted list that has not been set yet. 654 for (index = 0; index < count; index++) 655 { 656 if (!set[index]) 657 { 658 if (remainingPosition == s) 659 break; 660 661 remainingPosition++; 662 } 663 } 664 665 destination[index] = i; 666 set[index] = true; 667 } 668 return destination; 669 } 670 671 /** 672 * Given a long between 0 and the total number of permutations possible (see getBigTotalPermutations() for how to 673 * access this) and an int count of how many indices to find a permutation of, returns an array with the permutation 674 * of the indices described by the long as a special (factoradic) index into the possible permutations. You can get 675 * an index for a specific permutation with encodeBigPermutation() or by generating a random number between 0 and 676 * getBigTotalPermutations(), if you want it randomly. 677 * <br> 678 * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337 679 * @param encoded the index encoded as a BigInteger 680 * @param count a positive int that will be the size of the returned array 681 * @return the looked-up permutation as an int array with length equal to count 682 */ 683 public static int[] decodePermutation(BigInteger encoded, int count) 684 { 685 if(count <= 0) 686 return new int[0]; 687 BigInteger enc = encoded.mod(MathExtras.bigFactorial(count)); 688 int[] sequence = factoradicDecode(enc, count), destination = new int[count]; 689 //char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' }; //change for elements 690 691 //char[] permuted = new char[n]; //change for destination 692 boolean[] set = new boolean[count]; 693 694 for (int i = 0; i < count; i++) 695 { 696 int s = sequence[i]; 697 int remainingPosition = 0; 698 int index; 699 700 // Find the s'th position in the permuted list that has not been set yet. 701 for (index = 0; index < count; index++) 702 { 703 if (!set[index]) 704 { 705 if (remainingPosition == s) 706 break; 707 708 remainingPosition++; 709 } 710 } 711 712 destination[index] = i; 713 set[index] = true; 714 } 715 return destination; 716 } 717 718 /** 719 * Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access 720 * this) and an int count of how many indices to find a permutation of, returns an array with the permutation 721 * of the indices described by the long as a special (factoradic) index into the possible permutations. You can get 722 * an index for a specific permutation with encodePermutation() or by generating a random number between 0 and 723 * getTotalPermutations(), if you want it randomly. This variant adds an int to each item in the returned array, 724 * which may be useful if generating indices that don't start at 0. 725 * <br> 726 * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337 727 * @param encoded the index encoded as a long 728 * @param count an int between 1 and 20, inclusive, that will be the size of the returned array 729 * @param add an int to add to each item of the permutation 730 * @return the looked-up permutation as an int array with length equal to count 731 */ 732 public static int[] decodePermutation(long encoded, int count, int add) 733 { 734 int[] p = decodePermutation(encoded, count); 735 for (int i = 0; i < p.length; i++) { 736 p[i] += add; 737 } 738 return p; 739 } 740 741 /** 742 * Given a long between 0 and the total number of permutations possible (see getBigTotalPermutations() for how to 743 * access this) and an int count of how many indices to find a permutation of, returns an array with the permutation 744 * of the indices described by the long as a special (factoradic) index into the possible permutations. You can get 745 * an index for a specific permutation with encodeBigPermutation() or by generating a random number between 0 and 746 * getBigTotalPermutations(), if you want it randomly. This variant adds an int to each item in the returned array, 747 * which may be useful if generating indices that don't start at 0. 748 * <br> 749 * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337 750 * @param encoded the index encoded as a BigInteger 751 * @param count a positive int that will be the size of the returned array 752 * @param add an int to add to each item of the permutation 753 * @return the looked-up permutation as an int array with length equal to count 754 */ 755 public static int[] decodePermutation(BigInteger encoded, int count, int add) 756 { 757 int[] p = decodePermutation(encoded, count); 758 for (int i = 0; i < p.length; i++) { 759 p[i] += add; 760 } 761 return p; 762 } 763 764}