Package ca.cgjennings.math

Class Combinatorics

java.lang.Object

ca.cgjennings.math.Combinatorics

public class Combinatorics
extends java.lang.Object

Basic combinatoric mathematics support.

Author:

Chris Jennings

Method Summary

Modifier and Type	Method	Description
static long	combinations(int n, int r)	Return C(n, r), the number of sets of size r that can be created from a set of n objects.
static double	cumulativeDistribution(int successes, int trials, double pSuccess)	Returns the probability that out of trials attempts, a test that has a pSuccess probability of succeeding on each attempt will succeed at most successes times.
static long	factorial(int n)	Returns n! as a long value.
static long	permutations(int n, int r)	Return P(n, r), the number of lists of size r that can be created from a set of n objects.
static double	probabilityMass(int successes, int trials, double pSuccess)	Returns the probability that out of trials attempts, a test that has a pSuccess probability of succeeding on each attempt will succeed exactly successes times.
static double	upperCumulativeDistribution(int successes, int trials, double pSuccess)	Returns the probability that out of trials attempts, a test that has a pSuccess probability of succeeding on each attempt will succeed at least successes times.

Methods inherited from class java.lang.Object

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

Method Detail

factorial

public static final long factorial(int n)

Returns n! as a long value. In order to fit within a long, the value of n must not be greater than MAXIMUM_LONG_FACTORIAL.

Parameters:

n - the value to compute the factorial of

Returns:

the factorial of n, that is, n!

Throws:

java.lang.ArrayIndexOutOfBoundsException - if n < 0 or n > MAXIMUM_LONG_FACTORIAL

permutations

public static final long permutations(int n,
                                      int r)

Return P(n, r), the number of lists of size r that can be created from a set of n objects. Since this method counts the number of unique lists, the order in which the elements are selected is important. For example, the selection (1,2,3) and the selection (3,1,2) are both counted by this method. In order to fit within a long, the value of n must not be greater than MAXIMUM_LONG_FACTORIAL.

Example: The set {1,2,3} contains 3 elements. If we construct every possible list of length 2 that is composed of elements from that set, we would find that there are 6 possibilities:
(1,2), (1,3), (2,1), (2,3), (3,1) and (3,2)

Hence, permutations( 3, 2 ) would return 6.

Parameters:

n - the size of the set from which the elements of lists are to be taken

r - the size of the lists to created

Returns:

the number of unique lists that can be created

Throws:

java.lang.ArrayIndexOutOfBoundsException - if n < 0, n > MAXIMUM_LONG_FACTORIAL, r < 0, or r > n

combinations

public static final long combinations(int n,
                                      int r)

Return C(n, r), the number of sets of size r that can be created from a set of n objects. Since this method counts the number of unique sets, the order in which the elements are selected is not important. For example, the selection (1,2,3) and the selection (3,1,2) would only be counted once by this method. In order to fit within a long, the value of n must not be greater than MAXIMUM_LONG_FACTORIAL.

Example: The set {1,2,3} contains 3 elements. If we construct every possible set of length 2 that is composed of elements from that set, we would find that there are 3 possibilities:
{1,2}, {1,3}, {2,3}

Hence, combinations( 3, 2 ) would return 3.

Parameters:

n - the size of the set from which the elements of lists are to be taken

r - the size of the lists to created

Returns:

the number of unique lists that can be created

Throws:

java.lang.ArrayIndexOutOfBoundsException - if n < 0, n > MAXIMUM_LONG_FACTORIAL, r < 0, or r > n

probabilityMass

public static final double probabilityMass(int successes,
                                           int trials,
                                           double pSuccess)

Returns the probability that out of trials attempts, a test that has a pSuccess probability of succeeding on each attempt will succeed exactly successes times. For example, the probability of rolling 10 dice and having exactly 2 of those dice land on 6 is probabilityMass( 2, 10, 1/6d ) (about 0.29).

Parameters:

successes - the exact number of successes required

trials - the number of trials to attempt

pSuccess - the probability that a given trial will succeed

Returns:

the probability that exactly successes trials will succeed

Throws:

java.lang.IllegalArgumentException - if pSuccess is not in the range (0,1)

java.lang.ArrayIndexOutOfBoundsException - if n < 0, n > MAXIMUM_LONG_FACTORIAL, r < 0, or r > n

cumulativeDistribution

public static final double cumulativeDistribution(int successes,
                                                  int trials,
                                                  double pSuccess)

Returns the probability that out of trials attempts, a test that has a pSuccess probability of succeeding on each attempt will succeed at most successes times. For example, the probability of rolling 10 dice and having at most 2 of those dice land on 6 is cumulativeDistribution( 2, 10, 1/6d ) (about 0.78).

Parameters:

successes - the maximum number of successes allowed

trials - the number of trials to attempt

pSuccess - the probability that a given trial will succeed

Returns:

the probability that at most successes trials will succeed

Throws:

java.lang.IllegalArgumentException - if pSuccess is not in the range (0,1)

java.lang.ArrayIndexOutOfBoundsException - if n < 0, n > MAXIMUM_LONG_FACTORIAL, r < 0, or r > n

upperCumulativeDistribution

public static final double upperCumulativeDistribution(int successes,
                                                       int trials,
                                                       double pSuccess)

Returns the probability that out of trials attempts, a test that has a pSuccess probability of succeeding on each attempt will succeed at least successes times. For example, the probability of rolling 10 dice and having at least 2 of those dice land on 6 is upperCumulativeDistribution( 2, 10, 1/6d ) (about 0.52).

Mathematically, this value can be computed as:
upperCumulativeDistribution(s,t,p) = probabilityMass(s,t,p) + 1-cumulativeDistribution(s,t,p)

Note that this method may not compute the value in exactly this way, and so may return a slightly different result if comprared to the above.

Parameters:

successes - the minimum number of successes required

trials - the number of trials to attempt

pSuccess - the probability that a given trial will succeed

Returns:

the probability that at least successes trials will succeed

Throws:

java.lang.IllegalArgumentException - if pSuccess is not in the range (0,1)

java.lang.ArrayIndexOutOfBoundsException - if n < 0, n > MAXIMUM_LONG_FACTORIAL, r < 0, or r > n