Class CombinationGenerator<T>
- java.lang.Object
-
- org.uncommons.maths.combinatorics.CombinationGenerator<T>
-
- Type Parameters:
T
- The type of element that the combinations are made from.
- All Implemented Interfaces:
java.lang.Iterable<java.util.List<T>>
public class CombinationGenerator<T> extends java.lang.Object implements java.lang.Iterable<java.util.List<T>>
Combination generator for generating all combinations of a given size from the specified set of elements. For performance reasons, this implementation is restricted to operating with set sizes and combination lengths that produce no more than 2^63 different combinations.- See Also:
PermutationGenerator
-
-
Field Summary
Fields Modifier and Type Field Description private int[]
combinationIndices
private T[]
elements
private long
remainingCombinations
private long
totalCombinations
-
Constructor Summary
Constructors Constructor Description CombinationGenerator(java.util.Collection<T> elements, int combinationLength)
Create a combination generator that generates all combinations of a specified length from the given set.CombinationGenerator(T[] elements, int combinationLength)
Create a combination generator that generates all combinations of a specified length from the given set.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
generateNextCombinationIndices()
Generate the indices into the elements array for the next combination.long
getRemainingCombinations()
long
getTotalCombinations()
boolean
hasMore()
Are there more combinations?java.util.Iterator<java.util.List<T>>
iterator()
Provides a read-only iterator for iterating over the combinations generated by this object.T[]
nextCombinationAsArray()
Generate the next combination and return an array containing the appropriate elements.T[]
nextCombinationAsArray(T[] destination)
Generate the next combination and return an array containing the appropriate elements.java.util.List<T>
nextCombinationAsList()
Generate the next combination and return a list containing the appropriate elements.java.util.List<T>
nextCombinationAsList(java.util.List<T> destination)
Generate the next combination and return a list containing the appropriate elements.void
reset()
Reset the combination generator.
-
-
-
Field Detail
-
elements
private final T[] elements
-
combinationIndices
private final int[] combinationIndices
-
remainingCombinations
private long remainingCombinations
-
totalCombinations
private long totalCombinations
-
-
Constructor Detail
-
CombinationGenerator
public CombinationGenerator(T[] elements, int combinationLength)
Create a combination generator that generates all combinations of a specified length from the given set.- Parameters:
elements
- The set from which to generate combinations.combinationLength
- The length of the combinations to be generated.
-
CombinationGenerator
public CombinationGenerator(java.util.Collection<T> elements, int combinationLength)
Create a combination generator that generates all combinations of a specified length from the given set.- Parameters:
elements
- The set from which to generate combinations.combinationLength
- The length of the combinations to be generated.
-
-
Method Detail
-
reset
public final void reset()
Reset the combination generator.
-
getRemainingCombinations
public long getRemainingCombinations()
- Returns:
- The number of combinations not yet generated.
-
hasMore
public boolean hasMore()
Are there more combinations?- Returns:
- true if there are more combinations available, false otherwise.
-
getTotalCombinations
public long getTotalCombinations()
- Returns:
- The total number of combinations.
-
nextCombinationAsArray
public T[] nextCombinationAsArray()
Generate the next combination and return an array containing the appropriate elements.- Returns:
- An array containing the elements that make up the next combination.
- See Also:
nextCombinationAsArray(Object[])
,nextCombinationAsList()
-
nextCombinationAsArray
public T[] nextCombinationAsArray(T[] destination)
Generate the next combination and return an array containing the appropriate elements. 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 combinations. If thenextCombinationAsArray()
method is used it will create a new array every time. When iterating over combinations this will result in lots of short-lived objects that have to be garbage collected. This method allows a single array instance to be reused in such circumstances.- Parameters:
destination
- Provides an array to use to create the combination. The specified array must be the same length as a combination.- Returns:
- The provided array now containing the elements of the combination.
-
nextCombinationAsList
public java.util.List<T> nextCombinationAsList()
Generate the next combination and return a list containing the appropriate elements.- Returns:
- A list containing the elements that make up the next combination.
- See Also:
nextCombinationAsList(List)
,nextCombinationAsArray()
-
nextCombinationAsList
public java.util.List<T> nextCombinationAsList(java.util.List<T> destination)
Generate the next combination and return a list containing the appropriate elements. 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 combinations. If thenextCombinationAsList()
method is used it will create a new list every time. When iterating over combinations 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 combination.- Returns:
- The provided list now containing the elements of the combination.
-
generateNextCombinationIndices
private void generateNextCombinationIndices()
Generate the indices into the elements array for the next combination. The algorithm is from Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), p. 286.
-
iterator
public java.util.Iterator<java.util.List<T>> iterator()
Provides a read-only iterator for iterating over the combinations 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); CombinationGenerator<Integer> combinations = new CombinationGenerator(elements, 2); for (List<Integer> c : combinations) { // Do something with each combination. }
- Specified by:
iterator
in interfacejava.lang.Iterable<T>
- Returns:
- An iterator.
- Since:
- 1.1
-
-