Class Stirling
- java.lang.Object
-
- org.apache.commons.numbers.combinatorics.Stirling
-
public final class Stirling extends java.lang.Object
Computation of Stirling numbers.- Since:
- 1.2
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
Stirling.StirlingS1Cache
Precomputed Stirling numbers of the first kind.private static class
Stirling.StirlingS2Cache
Precomputed Stirling numbers of the second kind.
-
Field Summary
Fields Modifier and Type Field Description private static java.lang.String
S1_ERROR_FORMAT
Stirling S1 error message.private static int
S1_OVERFLOW_K_EQUALS_1
Overflow threshold for n when computing s(n, 1).private static int
S1_OVERFLOW_K_EQUALS_NM2
Overflow threshold for n when computing s(n, n-2).private static int
S1_OVERFLOW_K_EQUALS_NM3
Overflow threshold for n when computing s(n, n-3).private static java.lang.String
S2_ERROR_FORMAT
Stirling S2 error message.private static int
S2_OVERFLOW_K_EQUALS_NM2
Overflow threshold for n when computing S(n, n-2).private static int
S2_OVERFLOW_K_EQUALS_NM3
Overflow threshold for n when computing S(n, n-3).
-
Constructor Summary
Constructors Modifier Constructor Description private
Stirling()
Private constructor.
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description private static void
checkArguments(int n, int k)
Check0 <= k <= n
.private static void
checkN(int n, int k, int threshold, java.lang.String msgFormat)
Checkn <= threshold
, or else throw anArithmeticException
.private static long
productOver4(long a, long b)
Returna*b/4
without intermediate overflow.static long
stirlingS1(int n, int k)
Returns the signed Stirling number of the first kind, "s(n,k)
".static long
stirlingS2(int n, int k)
Returns the Stirling number of the second kind, "S(n,k)
", the number of ways of partitioning ann
-element set intok
non-empty subsets.
-
-
-
Field Detail
-
S1_ERROR_FORMAT
private static final java.lang.String S1_ERROR_FORMAT
Stirling S1 error message.- See Also:
- Constant Field Values
-
S2_ERROR_FORMAT
private static final java.lang.String S2_ERROR_FORMAT
Stirling S2 error message.- See Also:
- Constant Field Values
-
S1_OVERFLOW_K_EQUALS_1
private static final int S1_OVERFLOW_K_EQUALS_1
Overflow threshold for n when computing s(n, 1).- See Also:
- Constant Field Values
-
S1_OVERFLOW_K_EQUALS_NM2
private static final int S1_OVERFLOW_K_EQUALS_NM2
Overflow threshold for n when computing s(n, n-2).- See Also:
- Constant Field Values
-
S1_OVERFLOW_K_EQUALS_NM3
private static final int S1_OVERFLOW_K_EQUALS_NM3
Overflow threshold for n when computing s(n, n-3).- See Also:
- Constant Field Values
-
S2_OVERFLOW_K_EQUALS_NM2
private static final int S2_OVERFLOW_K_EQUALS_NM2
Overflow threshold for n when computing S(n, n-2).- See Also:
- Constant Field Values
-
S2_OVERFLOW_K_EQUALS_NM3
private static final int S2_OVERFLOW_K_EQUALS_NM3
Overflow threshold for n when computing S(n, n-3).- See Also:
- Constant Field Values
-
-
Method Detail
-
stirlingS1
public static long stirlingS1(int n, int k)
Returns the signed Stirling number of the first kind, "s(n,k)
". The number of permutations ofn
elements which contain exactlyk
permutation cycles is the nonnegative number:|s(n,k)| = (-1)^(n-k) s(n,k)
- Parameters:
n
- Size of the setk
- Number of permutation cycles (0 <= k <= n
)- Returns:
s(n,k)
- Throws:
java.lang.IllegalArgumentException
- ifn < 0
,k < 0
ork > n
.java.lang.ArithmeticException
- if some overflow happens, typically for n exceeding 20 (s(n,n-1) is handled specifically and does not overflow)
-
stirlingS2
public static long stirlingS2(int n, int k)
Returns the Stirling number of the second kind, "S(n,k)
", the number of ways of partitioning ann
-element set intok
non-empty subsets.- Parameters:
n
- Size of the setk
- Number of non-empty subsets (0 <= k <= n
)- Returns:
S(n,k)
- Throws:
java.lang.IllegalArgumentException
- ifn < 0
,k < 0
ork > n
.java.lang.ArithmeticException
- 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)
-
checkArguments
private static void checkArguments(int n, int k)
Check0 <= k <= n
.- Parameters:
n
- Nk
- K- Throws:
java.lang.IllegalArgumentException
- ifn < 0
,k < 0
ork > n
.
-
checkN
private static void checkN(int n, int k, int threshold, java.lang.String msgFormat)
Checkn <= threshold
, or else throw anArithmeticException
.- Parameters:
n
- Nk
- Kthreshold
- Threshold forn
msgFormat
- Error message format- Throws:
java.lang.ArithmeticException
- if overflow is expected to happen
-
productOver4
private static long productOver4(long a, long b)
Returna*b/4
without intermediate overflow. It is assumed that:- The coefficients a and b are positive
- The product (a*b) is an exact multiple of 4
- The result (a*b/4) is an exact integer that does not overflow a
long
A conditional branch is performed on the odd/even property of
b
. The branch is predictable ifb
is typically the same parity.- Parameters:
a
- Coefficient ab
- Coefficient b- Returns:
a*b/4
-
-