org.josef.science.math

Class Combinations<T>

java.lang.Object

org.josef.science.math.Combinations<T>

Type Parameters:

T - The type for the combinations.

@Status(stage=PRODUCTION,
        unitTests=COMPLETE)
 @Review(by="Kees Schotanus",
        at="2009-09-28")
 @ThreadSafety(level=NOT_THREAD_SAFE)
public final class Combinations<T>
extends Object

Mathematical utility class that handles combinations.
Combinations are unordered sets of elements. This class aids in creating combinations of a certain size (r) taken out of a set of elements (n). This is known as 'n choose r' or C(n,r). Consider the set {a,b,c,d,e}. What combinations can be made consisting of 3 elements? The answer is {a,b,c}, {a,b,d}, {a,b,e}, {a,c,d}, {a,c,e}, {a,d,e}, {b,c,d}, {b,c,e}, {b,d,e}, {c,d,e}. More formally the number of combinations can be expressed as:
n! / (r!(n-r)!), provided n >= r >= 0
Where n is the size of the set and r is the number of elements taken out of the set. To be mathematically complete the number of combinations when
n < 0 or r < 0 or r > n is 0.
To lookup more information about combinations on the Internet you may wish to use one or more of the following keywords: Binomial coefficient, combinatorics, Pascal's Triangle.
This class uses the Algorithm constructed by Keneth Rosen (Discrete Mathematics and Its Applications 4/E, Section 4.3). The algorithm is actually quite simple. Consider the example above about getting 3 elements out of a set of 5 elements {a,b,c,d,e}. When getting combinations of size r create an array of pointers with r elements and initialize the array with values of 0 to r - 1. Here is what this would look like:

 a, b, c, d, e
 0  1  2

As you can see a, b , c is the first combination. To get the second combination increase the last pointer. This looks like:

 a, b, c, d,  e
 0  1     2

Increase the last pointer again, this results in:

 a, b, c, d, e
 0  1        2

Now you can't increase the last pointer since it would be out of bounds. We have to increase the second pointer and let the third pointer point just after the second. This looks like:

 a, b, c, d, e
 0     1  2

You just have to repeat this process to get all combinations! Check out the source for more information about the algorithm, particularly for efficiently moving around all the pointers.
This class is suitable for large number of combinations. Since combinations are computed one at a time this class consumes very little memory. Due to the possibly large number of combinations the combinations are returned as an array for which no defensive copy has been made.

Version:

1.0 $Revision: 6488 $

Author:

Kees Schotanus

Method Summary

Modifier and Type	Method and Description
static BigInteger	countNumberOfCombinations(long n, long r) Calculates the number of combinations for 'n choose r'.
static <T> Iterator<T[]>	iterator(T[] set) Creates an Iterator that can be used to iterate over all possible combinations of elements out of the supplied set.
static <T> Iterator<T[]>	iterator(T[] set, int size) Creates an Iterator that can be used to iterate over all possible combinations where each combination is of the supplied size.

Methods inherited from class java.lang.Object

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

Method Detail

countNumberOfCombinations

public static BigInteger countNumberOfCombinations(long n,
                                                   long r)

Calculates the number of combinations for 'n choose r'.

Parameters:

n - Number of elements in the set.

r - Number of elements taken out of the set.

Returns:

Total number of combinations that can be formed. When n < 0 or r > n, 0 is returned.

iterator

public static <T> Iterator<T[]> iterator(T[] set)

Creates an Iterator that can be used to iterate over all possible combinations of elements out of the supplied set.
For the set {a,b,c,d,e} this iterator generates the combinations:
a,b,c,d,e,ab,ac,ad,ae,bc,bd,be,cd,ce,de,abc,abd,abe,acd,ace,ade,bcd,bce, bde,cde,abcd,abce,abde,acde,bcde,abcde
The combinations are ordered on size. Combinations of the same size are ordered lexicographically, provided the supplied set is ordered.
Note: The number of combinations can be calculated by 2^set. For a set consisting of 5 elements, 2⁵=32 combinations exist. This method however will give you an iterator that only gets 31 combinations since it does not contain the 'empty' combination.

Type Parameters:

T - Type of a single element of a combination.

Parameters:

set - The set containing all the elements.

Returns:

An iterator suitable for iterating over all possible combinations of elements out of the supplied set.

Throws:

IllegalArgumentException - the supplied set does not contain between 1 and MAX_SIZE_OF_SMALL_SET elements.

NullPointerException - When the supplied set is null.

iterator

public static <T> Iterator<T[]> iterator(T[] set,
                                         int size)

Creates an Iterator that can be used to iterate over all possible combinations where each combination is of the supplied size.
This iterator will return combinations in lexicographic order provided that the supplied set is in lexicographic order!
Depending upon the supplied set and size an efficient iterator is returned.

Type Parameters:

T - Type of a single element of a combination.

Parameters:

set - The set containing all the elements.

size - Size each combination should have.
The size should be in the range: [0 .. set.length()]

Returns:

An iterator suitable for iterating over the combinations of size elements.

Throws:

NullPointerException - When the supplied set is null.

IllegalArgumentException - When the supplied size is not in the range [0 .. set.length()]