Class Combinations

java.lang.Object

org.apache.commons.math3.util.Combinations

All Implemented Interfaces:

Iterable<int[]>

public class Combinations
extends Object
implements Iterable<int[]>

Utility to create combinations (n, k) of k elements in a set of n elements.

Since:

3.3

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static enum	Combinations.IterationOrder	Describes the type of iteration performed by the iterator.
private static class	Combinations.LexicographicComparator	Defines the lexicographic ordering of combinations, using the Combinations.LexicographicComparator.lexNorm(int[]) method.
private static class	Combinations.LexicographicIterator	Lexicographic combinations iterator.
private static class	Combinations.SingletonIterator	Iterator with just one element to handle degenerate cases (full array, empty array) for combination iterator.

Field Summary

Fields

Modifier and Type	Field	Description
private final Combinations.IterationOrder	iterationOrder	Iteration order.
private final int	k	Number of elements in each combination.
private final int	n	Size of the set from which combinations are drawn.

Constructor Summary

Constructors

Modifier	Constructor	Description
	Combinations(int n, int k)	Creates an instance whose range is the k-element subsets of {0, ..., n - 1} represented as int[] arrays.
private	Combinations(int n, int k, Combinations.IterationOrder iterationOrder)	Creates an instance whose range is the k-element subsets of {0, ..., n - 1} represented as int[] arrays.

Method Summary

Modifier and Type	Method	Description
Comparator<int[]>	comparator()	Defines a lexicographic ordering of combinations.
int	getK()	Gets the number of elements in each combination.
int	getN()	Gets the size of the set from which combinations are drawn.
Iterator<int[]>	iterator()

Methods inherited from class Object

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

Methods inherited from interface Iterable

forEach, spliterator

Field Details

n

private final int n

Size of the set from which combinations are drawn.

k

private final int k

Number of elements in each combination.

iterationOrder

private final Combinations.IterationOrder iterationOrder

Iteration order.

Constructor Details

Combinations

public Combinations(int n,
 int k)

Creates an instance whose range is the k-element subsets of {0, ..., n - 1} represented as int[] arrays.

The iteration order is lexicographic: the arrays returned by the iterator are sorted in descending order and they are visited in lexicographic order with significance from right to left. For example, new Combinations(4, 2).iterator() returns an iterator that will generate the following sequence of arrays on successive calls to next():
[0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]

If k == 0 an iterator containing an empty array is returned; if k == n an iterator containing [0, ..., n - 1] is returned.

Parameters:

n - Size of the set from which subsets are selected.

k - Size of the subsets to be enumerated.

Throws:

NotPositiveException - if n < 0.

NumberIsTooLargeException - if k > n.

Combinations

private Combinations(int n,
 int k,
 Combinations.IterationOrder iterationOrder)

Creates an instance whose range is the k-element subsets of {0, ..., n - 1} represented as int[] arrays.

If the iterationOrder argument is set to Combinations.IterationOrder.LEXICOGRAPHIC, the arrays returned by the iterator are sorted in descending order and they are visited in lexicographic order with significance from right to left. For example, new Combinations(4, 2).iterator() returns an iterator that will generate the following sequence of arrays on successive calls to next():
[0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]

If k == 0 an iterator containing an empty array is returned; if k == n an iterator containing [0, ..., n - 1] is returned.

Parameters:

n - Size of the set from which subsets are selected.

k - Size of the subsets to be enumerated.

iterationOrder - Specifies the iteration order.

Throws:

NotPositiveException - if n < 0.

NumberIsTooLargeException - if k > n.

Method Details

getN

public int getN()

Gets the size of the set from which combinations are drawn.

Returns:

the size of the universe.

getK

public int getK()

Gets the number of elements in each combination.

Returns:

the size of the subsets to be enumerated.

iterator

public Iterator<int[]> iterator()

Specified by:

iterator in interface Iterable<int[]>

comparator

public Comparator<int[]> comparator()

Defines a lexicographic ordering of combinations. The returned comparator allows to compare any two combinations that can be produced by this instance's iterator. Its compare(int[],int[]) method will throw exceptions if passed combinations that are inconsistent with this instance:

• DimensionMismatchException if the array lengths are not equal to k,
• OutOfRangeException if an element of the array is not within the interval [0, n).

Returns:

a lexicographic comparator.