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