T
- The type of element that the permutation will consist of.public class PermutationGenerator<T>
extends java.lang.Object
implements java.lang.Iterable<java.util.List<T>>, java.io.Serializable
BigInteger
).
CombinationGenerator
,
Serialized FormConstructor and Description |
---|
PermutationGenerator(java.util.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.
|
Modifier and Type | Method and Description |
---|---|
static int[] |
decodePermutation(java.math.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(java.math.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.
|
java.util.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.
|
java.util.List<T> |
decodePermutation(long encoded,
java.util.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 java.math.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(java.util.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 java.math.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?
|
java.util.Iterator<java.util.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.
|
java.util.List<T> |
nextPermutationAsList()
Generate the next permutation and return a list containing
the elements in the appropriate order.
|
java.util.List<T> |
nextPermutationAsList(java.util.List<T> destination)
Generate the next permutation and return a list containing
the elements in the appropriate order.
|
void |
reset()
Resets the generator state.
|
public PermutationGenerator(T[] elements)
elements
- The elements to permute; will be modified, so this should be copied beforehandpublic PermutationGenerator(java.util.Collection<T> elements, T[] filler)
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.public final void reset()
public long getRemainingPermutations()
public long getTotalPermutations()
public static long getTotalPermutations(int count)
count
- the number of elements (typically indices) you want to find a permutation ofpublic static java.math.BigInteger getBigTotalPermutations(int count)
count
- the number of elements (typically indices) you want to find a permutation ofpublic boolean hasMore()
public T[] nextPermutationAsArray(T[] destination)
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.public java.util.List<T> nextPermutationAsList()
nextPermutationAsList(List)
public java.util.List<T> nextPermutationAsList(java.util.List<T> destination)
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.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.public long encodePermutation(T[] perm)
perm
- an array of T that must be a valid permutation of this object's elementspublic long encodePermutation(java.util.List<T> perm)
perm
- a List of T that must be a valid permutation of this object's elementspublic T[] decodePermutation(long encoded, T[] destination)
encoded
- the index encoded as a longdestination
- an array of T that must have equivalent length to the elements this was constructed withpublic java.util.List<T> decodePermutation(long encoded)
encoded
- the index encoded as a longpublic java.util.List<T> decodePermutation(long encoded, java.util.List<T> destination)
encoded
- the index encoded as a longdestination
- a List of T that must have equivalent size to the elements this was constructed withpublic java.util.Iterator<java.util.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. }
iterator
in interface java.lang.Iterable<java.util.List<T>>
public static long encodePermutation(int[] perm)
encodeBigPermutation(int[])
instead.
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)public static java.math.BigInteger encodeBigPermutation(int[] perm)
encodePermutation(T[])
instead to get a 64-bit encoding.
perm
- an array of int that is a permutation of the range from 0 (inclusive) to perm.length (exclusive)public static int[] decodePermutation(long encoded, int count)
encoded
- the index encoded as a longcount
- an int between 1 and 20, inclusive, that will be the size of the returned arraypublic static int[] decodePermutation(java.math.BigInteger encoded, int count)
encoded
- the index encoded as a BigIntegercount
- a positive int that will be the size of the returned arraypublic static int[] decodePermutation(long encoded, int count, int add)
encoded
- the index encoded as a longcount
- an int between 1 and 20, inclusive, that will be the size of the returned arrayadd
- an int to add to each item of the permutationpublic static int[] decodePermutation(java.math.BigInteger encoded, int count, int add)
encoded
- the index encoded as a BigIntegercount
- a positive int that will be the size of the returned arrayadd
- an int to add to each item of the permutationCopyright © Eben Howard 2012–2022. All rights reserved.