org.apache.commons.math3.util

Class CombinatoricsUtils

java.lang.Object

org.apache.commons.math3.util.CombinatoricsUtils

public final class CombinatoricsUtils
extends java.lang.Object

Combinatorial utilities.

Since:

3.3

Field Summary

Fields

Modifier and Type	Field and Description
(package private) static long[]	FACTORIALS All long-representable factorials
(package private) static java.util.concurrent.atomic.AtomicReference<long[][]>	STIRLING_S2 Stirling numbers of the second kind.

Constructor Summary

Constructors

Modifier	Constructor and Description
private	CombinatoricsUtils() Private constructor (class contains only static methods).

Method Summary

Methods

Modifier and Type	Method and Description
static long	binomialCoefficient(int n, int k) Returns an exact representation of the Binomial Coefficient, "n choose k", the number of k-element subsets that can be selected from an n-element set.
static double	binomialCoefficientDouble(int n, int k) Returns a double representation of the Binomial Coefficient, "n choose k", the number of k-element subsets that can be selected from an n-element set.
static double	binomialCoefficientLog(int n, int k) Returns the natural log of the Binomial Coefficient, "n choose k", the number of k-element subsets that can be selected from an n-element set.
static void	checkBinomial(int n, int k) Check binomial preconditions.
static java.util.Iterator<int[]>	combinationsIterator(int n, int k) Returns an iterator whose range is the k-element subsets of {0, ..., n - 1} represented as int[] arrays.
static long	factorial(int n) Returns n!.
static double	factorialDouble(int n) Compute n!, the factorial of n (the product of the numbers 1 to n), as a double.
static double	factorialLog(int n) Compute the natural logarithm of the factorial of n.
static long	stirlingS2(int n, int k) Returns the Stirling number of the second kind, "S(n,k)", the number of ways of partitioning an n-element set into k non-empty subsets.

Methods inherited from class java.lang.Object

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

Field Detail

FACTORIALS

static final long[] FACTORIALS

All long-representable factorials

STIRLING_S2

static final java.util.concurrent.atomic.AtomicReference<long[][]> STIRLING_S2

Stirling numbers of the second kind.

Constructor Detail

CombinatoricsUtils

private CombinatoricsUtils()

Private constructor (class contains only static methods).

Method Detail

binomialCoefficient

public static long binomialCoefficient(int n,
                       int k)
                                throws NotPositiveException,
                                       NumberIsTooLargeException,
                                       MathArithmeticException

Returns an exact representation of the Binomial Coefficient, "n choose k", the number of k-element subsets that can be selected from an n-element set.

Preconditions:

• 0 <= k <= n (otherwise MathIllegalArgumentException is thrown)
• The result is small enough to fit into a long. The largest value of n for which all coefficients are < Long.MAX_VALUE is 66. If the computed value exceeds Long.MAX_VALUE an ArithMeticException is thrown.

Parameters:

n - the size of the set

k - the size of the subsets to be counted

Returns:

n choose k

Throws:

NotPositiveException - if n < 0.

NumberIsTooLargeException - if k > n.

MathArithmeticException - if the result is too large to be represented by a long integer.

binomialCoefficientDouble

public static double binomialCoefficientDouble(int n,
                               int k)
                                        throws NotPositiveException,
                                               NumberIsTooLargeException,
                                               MathArithmeticException

Returns a double representation of the Binomial Coefficient, "n choose k", the number of k-element subsets that can be selected from an n-element set.

Preconditions:

• 0 <= k <= n (otherwise IllegalArgumentException is thrown)
• The result is small enough to fit into a double. The largest value of n for which all coefficients are < Double.MAX_VALUE is 1029. If the computed value exceeds Double.MAX_VALUE, Double.POSITIVE_INFINITY is returned

Parameters:

n - the size of the set

k - the size of the subsets to be counted

Returns:

n choose k

Throws:

NotPositiveException - if n < 0.

NumberIsTooLargeException - if k > n.

MathArithmeticException - if the result is too large to be represented by a long integer.

binomialCoefficientLog

public static double binomialCoefficientLog(int n,
                            int k)
                                     throws NotPositiveException,
                                            NumberIsTooLargeException,
                                            MathArithmeticException

Returns the natural log of the Binomial Coefficient, "n choose k", the number of k-element subsets that can be selected from an n-element set.

Preconditions:

• 0 <= k <= n (otherwise IllegalArgumentException is thrown)

Parameters:

n - the size of the set

k - the size of the subsets to be counted

Returns:

n choose k

Throws:

NotPositiveException - if n < 0.

NumberIsTooLargeException - if k > n.

MathArithmeticException - if the result is too large to be represented by a long integer.

factorial

public static long factorial(int n)
                      throws NotPositiveException,
                             MathArithmeticException

Returns n!. Shorthand for n Factorial, the product of the numbers 1,...,n.

Preconditions:

• n >= 0 (otherwise IllegalArgumentException is thrown)
• The result is small enough to fit into a long. The largest value of n for which n! < Long.MAX_VALUE} is 20. If the computed value exceeds Long.MAX_VALUE an ArithMeticException is thrown.

Parameters:

n - argument

Returns:

n!

Throws:

MathArithmeticException - if the result is too large to be represented by a long.

NotPositiveException - if n < 0.

MathArithmeticException - if n > 20: The factorial value is too large to fit in a long.

factorialDouble

public static double factorialDouble(int n)
                              throws NotPositiveException

Compute n!, the factorial of n (the product of the numbers 1 to n), as a double. The result should be small enough to fit into a double: The largest n for which n! < Double.MAX_VALUE is 170. If the computed value exceeds Double.MAX_VALUE, Double.POSITIVE_INFINITY is returned.

Parameters:

n - Argument.

Returns:

n!

Throws:

NotPositiveException - if n < 0.

factorialLog

public static double factorialLog(int n)
                           throws NotPositiveException

Compute the natural logarithm of the factorial of n.

Parameters:

n - Argument.

Returns:

n!

Throws:

NotPositiveException - if n < 0.

stirlingS2

public static long stirlingS2(int n,
              int k)
                       throws NotPositiveException,
                              NumberIsTooLargeException,
                              MathArithmeticException

Returns the Stirling number of the second kind, "S(n,k)", the number of ways of partitioning an n-element set into k non-empty subsets.

The preconditions are 0 <= k <= n (otherwise NotPositiveException is thrown)

Parameters:

n - the size of the set

k - the number of non-empty subsets

Returns:

S(n,k)

Throws:

NotPositiveException - if k < 0.

NumberIsTooLargeException - if k > n.

MathArithmeticException - if some overflow happens, typically for n exceeding 25 and k between 20 and n-2 (S(n,n-1) is handled specifically and does not overflow)

Since:

3.1

combinationsIterator

public static java.util.Iterator<int[]> combinationsIterator(int n,
                                             int k)

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

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, combinationsIterator(4, 2) 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 and 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.

Returns:

an iterator over the k-sets in n.

Throws:

NotPositiveException - if n < 0.

NumberIsTooLargeException - if k > n.

checkBinomial

public static void checkBinomial(int n,
                 int k)
                          throws NumberIsTooLargeException,
                                 NotPositiveException

Check binomial preconditions.

Parameters:

n - Size of the set.

k - Size of the subsets to be counted.

Throws:

NotPositiveException - if n < 0.

NumberIsTooLargeException - if k > n.