Package org.apache.commons.math3.util

Class CombinatoricsUtils

  • public final class CombinatoricsUtils
extends java.lang.Object
    Combinatorial utilities.
    Since:
    3.3

    • Field Summary

      Fields 
      Modifier and Type Field 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 Description
      private CombinatoricsUtils()
      Private constructor (class contains only static methods).

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method 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 a MathArithMeticException 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 less than 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.

      • 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 MathIllegalArgumentException is thrown)
        • The result is small enough to fit into a 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.

        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! does not exceed 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.

      • 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.