public final class CombinatoricsUtils extends Object
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 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)
|
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. |
public static long binomialCoefficient(int n, int k) throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException
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)long
. The
largest value of n
for which all coefficients are
< Long.MAX_VALUE
is 66. If the computed value exceeds
Long.MAX_VALUE
a MathArithMeticException
is
thrown.n
- the size of the setk
- the size of the subsets to be countedn choose k
NotPositiveException
- if n < 0
.NumberIsTooLargeException
- if k > n
.MathArithmeticException
- if the result is too large to be
represented by a long integer.public static double binomialCoefficientDouble(int n, int k) throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException
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)double
. The
largest value of n
for which all coefficients are less than
Double.MAX_VALUE is 1029. If the computed value exceeds Double.MAX_VALUE,
Double.POSITIVE_INFINITY is returnedn
- the size of the setk
- the size of the subsets to be countedn choose k
NotPositiveException
- if n < 0
.NumberIsTooLargeException
- if k > n
.MathArithmeticException
- if the result is too large to be
represented by a long integer.public static double binomialCoefficientLog(int n, int k) throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException
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
MathIllegalArgumentException
is thrown)n
- the size of the setk
- the size of the subsets to be countedn choose k
NotPositiveException
- if n < 0
.NumberIsTooLargeException
- if k > n
.MathArithmeticException
- if the result is too large to be
represented by a long integer.public static long factorial(int n) throws NotPositiveException, MathArithmeticException
n
Factorial, the
product of the numbers 1,...,n
.
Preconditions:
n >= 0
(otherwise
MathIllegalArgumentException
is thrown)long
. The
largest value of n
for which n!
does not exceed
Long.MAX_VALUE} is 20. If the computed value exceeds Long.MAX_VALUE
an MathArithMeticException
is thrown.n
- argumentn!
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
.public static double factorialDouble(int n) throws NotPositiveException
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!
does not exceed
Double.MAX_VALUE
is 170. If the computed value exceeds
Double.MAX_VALUE
, Double.POSITIVE_INFINITY
is returned.n
- Argument.n!
NotPositiveException
- if n < 0
.public static double factorialLog(int n) throws NotPositiveException
n
.n
- Argument.n!
NotPositiveException
- if n < 0
.public static long stirlingS2(int n, int k) throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException
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)
n
- the size of the setk
- the number of non-empty subsetsS(n,k)
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)public static Iterator<int[]> combinationsIterator(int n, int k)
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.
n
- Size of the set from which subsets are selected.k
- Size of the subsets to be enumerated.iterator
over the k-sets in n.NotPositiveException
- if n < 0
.NumberIsTooLargeException
- if k > n
.public static void checkBinomial(int n, int k) throws NumberIsTooLargeException, NotPositiveException
n
- Size of the set.k
- Size of the subsets to be counted.NotPositiveException
- if n < 0
.NumberIsTooLargeException
- if k > n
.Copyright © 2003–2016 The Apache Software Foundation. All rights reserved.