Package squidpony.squidmath

Class PermutationGenerator<T>

java.lang.Object
squidpony.squidmath.PermutationGenerator<T>
Type Parameters:
T - The type of element that the permutation will consist of.
All Implemented Interfaces:
Serializable, Iterable<List<T>>
public class PermutationGenerator<T>
extends Object
implements Iterable<List<T>>, Serializable
Permutation generator for generating all permutations for all sets up to 20 elements in size. While 20 may seem a low limit, bear in mind that the number of permutations of a set of size n is n! For a set of 21 items, the number of permutations is bigger than can be stored in Java's 64-bit long integer data type. Therefore it seems unlikely that you could ever generate, let alone process, all of the permutations in a reasonable time frame. For this reason the implementation is optimised for sets of size 20 or less (this affords better performance by allowing primitive numeric types to be used for calculations rather than BigInteger).
Originally part of the Uncommon Maths software package.
Author:
Daniel Dyer (modified from the original version written by Michael Gilleland of Merriam Park Software - http://www.merriampark.com/perm.htm).
See Also:
CombinationGenerator, Serialized Form

  • Constructor Summary

    Constructors 
    Constructor Description
    PermutationGenerator​(Collection<T> elements, T[] filler)
    Permutation generator that generates all possible orderings of the elements in the specified set.
    PermutationGenerator​(T[] elements)
    Permutation generator that generates all possible orderings of the elements in the specified set.

  • Method Summary

    Modifier and Type Method Description
    List<T> decodePermutation​(long encoded)
    Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access this), creates a List filled with the permutation described by the long as a special (factoradic) index into the possible permutations.
    static int[] decodePermutation​(long encoded, int count)
    Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access this) and an int count of how many indices to find a permutation of, returns an array with the permutation of the indices described by the long as a special (factoradic) index into the possible permutations.
    static int[] decodePermutation​(long encoded, int count, int add)
    Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access this) and an int count of how many indices to find a permutation of, returns an array with the permutation of the indices described by the long as a special (factoradic) index into the possible permutations.
    List<T> decodePermutation​(long encoded, List<T> destination)
    Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access this) and a List of T with the same length as the elements this was constructed with, fills the List with the permutation described by the long as a special (factoradic) index into the possible permutations.
    T[] decodePermutation​(long encoded, T[] destination)
    Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access this) and an array of T with the same length as the elements this was constructed with, fills the array with the permutation described by the long as a special (factoradic) index into the possible permutations.
    static int[] decodePermutation​(BigInteger encoded, int count)
    Given a long between 0 and the total number of permutations possible (see getBigTotalPermutations() for how to access this) and an int count of how many indices to find a permutation of, returns an array with the permutation of the indices described by the long as a special (factoradic) index into the possible permutations.
    static int[] decodePermutation​(BigInteger encoded, int count, int add)
    Given a long between 0 and the total number of permutations possible (see getBigTotalPermutations() for how to access this) and an int count of how many indices to find a permutation of, returns an array with the permutation of the indices described by the long as a special (factoradic) index into the possible permutations.
    static BigInteger encodeBigPermutation​(int[] perm)
    Given an array of int that constitutes a permutation of indices, where no element in perm is repeated and all ints are less than perm.length, finds the specific index of the permutation given a factoradic numbering scheme (not used by the rest of this class, except the decodePermutation() method).
    static long encodePermutation​(int[] perm)
    Given an array of int that constitutes a permutation of indices, where no element in perm is repeated and all ints are less than perm.length, finds the specific index of the permutation given a factoradic numbering scheme (not used by the rest of this class, except the decodePermutation() method).
    long encodePermutation​(List<T> perm)
    Given a List of T that constitutes a permutation of the elements this was constructed with, finds the specific index of the permutation given a factoradic numbering scheme (not used by the rest of this class, except the decodePermutation() method).
    long encodePermutation​(T[] perm)
    Given an array of T that constitutes a permutation of the elements this was constructed with, finds the specific index of the permutation given a factoradic numbering scheme (not used by the rest of this class, except the decodePermutation() method).
    static BigInteger getBigTotalPermutations​(int count)
    Returns the total number of unique permutations that can be generated for the given count of permute-able elements.
    long getRemainingPermutations()
    Returns the number of permutations not yet generated.
    long getTotalPermutations()
    Returns the total number of unique permutations that can be generated for the given set of elements.
    static long getTotalPermutations​(int count)
    Returns the total number of unique permutations that can be generated for the given count of permute-able elements.
    boolean hasMore()
    Are there more permutations that have not yet been returned?
    Iterator<List<T>> iterator()
    Provides a read-only iterator for iterating over the permutations generated by this object.
    T[] nextPermutationAsArray​(T[] destination)
    Generate the next permutation and return an array containing the elements in the appropriate order.
    List<T> nextPermutationAsList()
    Generate the next permutation and return a list containing the elements in the appropriate order.
    List<T> nextPermutationAsList​(List<T> destination)
    Generate the next permutation and return a list containing the elements in the appropriate order.
    void reset()
    Resets the generator state.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Constructor Details

    • PermutationGenerator

      public PermutationGenerator​(T[] elements)
      Permutation generator that generates all possible orderings of the elements in the specified set.
      Parameters:
      elements - The elements to permute; will be modified, so this should be copied beforehand

    • PermutationGenerator

      public PermutationGenerator​(Collection<T> elements, T[] filler)
      Permutation generator that generates all possible orderings of the elements in the specified set.
      Parameters:
      elements - The elements to permute.
      filler - An array of T with the same length as elements or less (often 0); needed because GWT can't create a generic array. If elements is not a Collection defined in the JDK (by GWT), then this should have exactly the same length as elements, since GWT can create larger versions of an array on its own, but our code can't easily.

  • Method Details

    • reset

      public final void reset()
      Resets the generator state.

    • getRemainingPermutations

      public long getRemainingPermutations()
      Returns the number of permutations not yet generated.
      Returns:
      The number of unique permutations still to be generated.

    • getTotalPermutations

      public long getTotalPermutations()
      Returns the total number of unique permutations that can be generated for the given set of elements.
      Returns:
      The total number of permutations.

    • getTotalPermutations

      public static long getTotalPermutations​(int count)
      Returns the total number of unique permutations that can be generated for the given count of permute-able elements. Typically used with the static methods of this class that find permutation indices.
      Parameters:
      count - the number of elements (typically indices) you want to find a permutation of
      Returns:
      The total number of permutations.

    • getBigTotalPermutations

      public static BigInteger getBigTotalPermutations​(int count)
      Returns the total number of unique permutations that can be generated for the given count of permute-able elements. Typically used with the static methods of this class that find permutation indices and involve BigInteger values.
      Parameters:
      count - the number of elements (typically indices) you want to find a permutation of
      Returns:
      The total number of permutations.

    • hasMore

      public boolean hasMore()
      Are there more permutations that have not yet been returned?
      Returns:
      true if there are more permutations, false otherwise.

    • nextPermutationAsArray

      public T[] nextPermutationAsArray​(T[] destination)
      Generate the next permutation and return an array containing the elements in the appropriate order. This overloaded method allows the caller to provide an array that will be used and returned. The purpose of this is to improve performance when iterating over permutations. This method allows a single array instance to be reused.
      Parameters:
      destination - Provides an array to use to create the permutation. The specified array must be the same length as a permutation. This is the array that will be returned, once it has been filled with the elements in the appropriate order.
      Returns:
      The next permutation as an array.

    • nextPermutationAsList

      public List<T> nextPermutationAsList()
      Generate the next permutation and return a list containing the elements in the appropriate order.
      Returns:
      The next permutation as a list.
      See Also:
      nextPermutationAsList(List)

    • nextPermutationAsList

      public List<T> nextPermutationAsList​(List<T> destination)
      Generate the next permutation and return a list containing the elements in the appropriate order. This overloaded method allows the caller to provide a list that will be used and returned. The purpose of this is to improve performance when iterating over permutations. If the nextPermutationAsList() method is used it will create a new list every time. When iterating over permutations this will result in lots of short-lived objects that have to be garbage collected. This method allows a single list instance to be reused in such circumstances.
      Parameters:
      destination - Provides a list to use to create the permutation. This is the list that will be returned, once it has been filled with the elements in the appropriate order.
      Returns:
      The next permutation as a list.

    • encodePermutation

      public long encodePermutation​(T[] perm)
      Given an array of T that constitutes a permutation of the elements this was constructed with, finds the specific index of the permutation given a factoradic numbering scheme (not used by the rest of this class, except the decodePermutation() method). The index can be passed to decodePermutation to reproduce the permutation passed to this, or modified and then passed to decodePermutation(). Determines equality by identity, not by .equals(), so that equivalent values that have different references/identities can appear in the permuted elements.
      Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
      Parameters:
      perm - an array of T that must be a valid permutation of this object's elements
      Returns:
      an encoded number that can be used to reconstruct the permutation when passed to decodePermutation()

    • encodePermutation

      public long encodePermutation​(List<T> perm)
      Given a List of T that constitutes a permutation of the elements this was constructed with, finds the specific index of the permutation given a factoradic numbering scheme (not used by the rest of this class, except the decodePermutation() method). The index can be passed to decodePermutation to reproduce the permutation passed to this, or modified and then passed to decodePermutation(). Determines equality by identity, not by .equals(), so that equivalent values that have different references/identities can appear in the permuted elements.
      Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
      Parameters:
      perm - a List of T that must be a valid permutation of this object's elements
      Returns:
      an encoded number that can be used to reconstruct the permutation when passed to decodePermutation()

    • decodePermutation

      public T[] decodePermutation​(long encoded, T[] destination)
      Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access this) and an array of T with the same length as the elements this was constructed with, fills the array with the permutation described by the long as a special (factoradic) index into the possible permutations. You can get an index for a specific permutation with encodePermutation() or by generating a random number between 0 and getTotalPermutations(), if you want it randomly.
      Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
      Parameters:
      encoded - the index encoded as a long
      destination - an array of T that must have equivalent length to the elements this was constructed with
      Returns:
      the looked-up permutation, which is the same value destination will be assigned

    • decodePermutation

      public List<T> decodePermutation​(long encoded)
      Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access this), creates a List filled with the permutation described by the long as a special (factoradic) index into the possible permutations. You can get an index for a specific permutation with encodePermutation() or by generating a random number between 0 and getTotalPermutations(), if you want it randomly.
      Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
      Parameters:
      encoded - the index encoded as a long
      Returns:
      a List of T that corresponds to the permutation at the encoded index

    • decodePermutation

      public List<T> decodePermutation​(long encoded, List<T> destination)
      Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access this) and a List of T with the same length as the elements this was constructed with, fills the List with the permutation described by the long as a special (factoradic) index into the possible permutations. You can get an index for a specific permutation with encodePermutation() or by generating a random number between 0 and getTotalPermutations(), if you want it randomly.
      Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
      Parameters:
      encoded - the index encoded as a long
      destination - a List of T that must have equivalent size to the elements this was constructed with
      Returns:
      the looked-up permutation, which is the same value destination will be assigned

    • iterator

      public Iterator<List<T>> iterator()

      Provides a read-only iterator for iterating over the permutations generated by this object. This method is the implementation of the Iterable interface that permits instances of this class to be used with the new-style for loop.

      For example:

       List<Integer> elements = Arrays.asList(1, 2, 3);
 PermutationGenerator<Integer> permutations = new PermutationGenerator(elements);
 for (List<Integer> p : permutations)
 {
     // Do something with each permutation.
 }
      Specified by:
      iterator in interface Iterable<T>
      Returns:
      An iterator.
      Since:
      1.1

    • encodePermutation

      public static long encodePermutation​(int[] perm)
      Given an array of int that constitutes a permutation of indices, where no element in perm is repeated and all ints are less than perm.length, finds the specific index of the permutation given a factoradic numbering scheme (not used by the rest of this class, except the decodePermutation() method). The index can be passed to decodePermutation to reproduce the index permutation passed to this, or modified and then passed to decodePermutation().
      If perm is more than 20 items in length, you should use encodeBigPermutation(int[]) instead.
      Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
      Parameters:
      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)
      Returns:
      an encoded number that can be used to reconstruct the permutation when passed to decodePermutation()

    • encodeBigPermutation

      public static BigInteger encodeBigPermutation​(int[] perm)
      Given an array of int that constitutes a permutation of indices, where no element in perm is repeated and all ints are less than perm.length, finds the specific index of the permutation given a factoradic numbering scheme (not used by the rest of this class, except the decodePermutation() method). The index can be passed to decodePermutation to reproduce the index permutation passed to this, or modified and then passed to decodePermutation().
      If perm is 20 items or less in length, you can use encodePermutation(T[]) instead to get a 64-bit encoding.
      Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
      Parameters:
      perm - an array of int that is a permutation of the range from 0 (inclusive) to perm.length (exclusive)
      Returns:
      an encoded number that can be used to reconstruct the permutation when passed to decodePermutation()

    • decodePermutation

      public static int[] decodePermutation​(long encoded, int count)
      Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access this) and an int count of how many indices to find a permutation of, returns an array with the permutation of the indices described by the long as a special (factoradic) index into the possible permutations. You can get an index for a specific permutation with encodePermutation() or by generating a random number between 0 and getTotalPermutations(), if you want it randomly.
      Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
      Parameters:
      encoded - the index encoded as a long
      count - an int between 1 and 20, inclusive, that will be the size of the returned array
      Returns:
      the looked-up permutation as an int array with length equal to count

    • decodePermutation

      public static int[] decodePermutation​(BigInteger encoded, int count)
      Given a long between 0 and the total number of permutations possible (see getBigTotalPermutations() for how to access this) and an int count of how many indices to find a permutation of, returns an array with the permutation of the indices described by the long as a special (factoradic) index into the possible permutations. You can get an index for a specific permutation with encodeBigPermutation() or by generating a random number between 0 and getBigTotalPermutations(), if you want it randomly.
      Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
      Parameters:
      encoded - the index encoded as a BigInteger
      count - a positive int that will be the size of the returned array
      Returns:
      the looked-up permutation as an int array with length equal to count

    • decodePermutation

      public static int[] decodePermutation​(long encoded, int count, int add)
      Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access this) and an int count of how many indices to find a permutation of, returns an array with the permutation of the indices described by the long as a special (factoradic) index into the possible permutations. You can get an index for a specific permutation with encodePermutation() or by generating a random number between 0 and getTotalPermutations(), if you want it randomly. This variant adds an int to each item in the returned array, which may be useful if generating indices that don't start at 0.
      Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
      Parameters:
      encoded - the index encoded as a long
      count - an int between 1 and 20, inclusive, that will be the size of the returned array
      add - an int to add to each item of the permutation
      Returns:
      the looked-up permutation as an int array with length equal to count

    • decodePermutation

      public static int[] decodePermutation​(BigInteger encoded, int count, int add)
      Given a long between 0 and the total number of permutations possible (see getBigTotalPermutations() for how to access this) and an int count of how many indices to find a permutation of, returns an array with the permutation of the indices described by the long as a special (factoradic) index into the possible permutations. You can get an index for a specific permutation with encodeBigPermutation() or by generating a random number between 0 and getBigTotalPermutations(), if you want it randomly. This variant adds an int to each item in the returned array, which may be useful if generating indices that don't start at 0.
      Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
      Parameters:
      encoded - the index encoded as a BigInteger
      count - a positive int that will be the size of the returned array
      add - an int to add to each item of the permutation
      Returns:
      the looked-up permutation as an int array with length equal to count