Class CombinatoricsUtils


  • public final class CombinatoricsUtils
    extends Object
    Combinatorial utilities.
    • Field Detail

      • MAX_BELL

        public static final int MAX_BELL
        Maximum index of Bell number that fits into a long.
        Since:
        2.2
        See Also:
        Constant Field Values
    • Method Detail

      • binomialCoefficient

        public static long binomialCoefficient​(int n,
                                               int k)
                                        throws MathIllegalArgumentException,
                                               MathRuntimeException
        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 MathRuntimeException is thrown.
        Parameters:
        n - the size of the set
        k - the size of the subsets to be counted
        Returns:
        n choose k
        Throws:
        MathIllegalArgumentException - if n < 0.
        MathIllegalArgumentException - if k > n.
        MathRuntimeException - if the result is too large to be represented by a long integer.
      • binomialCoefficientDouble

        public static double binomialCoefficientDouble​(int n,
                                                       int k)
                                                throws MathIllegalArgumentException,
                                                       MathRuntimeException
        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:
        MathIllegalArgumentException - if n < 0.
        MathIllegalArgumentException - if k > n.
        MathRuntimeException - if the result is too large to be represented by a long integer.
      • factorial

        public static long factorial​(int n)
                              throws MathIllegalArgumentException
        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 MathRuntimeException is thrown.
        Parameters:
        n - argument
        Returns:
        n!
        Throws:
        MathRuntimeException - if the result is too large to be represented by a long.
        MathIllegalArgumentException - if n < 0.
        MathIllegalArgumentException - if n > 20: The factorial value is too large to fit in a long.
      • factorialDouble

        public static double factorialDouble​(int n)
                                      throws MathIllegalArgumentException
        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:
        MathIllegalArgumentException - if n < 0.
      • combinationsIterator

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

        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:
        MathIllegalArgumentException - if n < 0.
        MathIllegalArgumentException - if k > n.
      • bellNumber

        public static long bellNumber​(int n)
        Compute the Bell number (number of partitions of a set).
        Parameters:
        n - number of elements of the set
        Returns:
        Bell number Bₙ
        Since:
        2.2
      • partitions

        public static <T> Stream<List<T>[]> partitions​(List<T> list)
        Generate a stream of partitions of a list.

        This method implements the iterative algorithm described in Short Note: A Fast Iterative Algorithm for Generating Set Partitions by B. Djokić, M. Miyakawa, S. Sekiguchi, I. Semba, and I. Stojmenović (The Computer Journal, Volume 32, Issue 3, 1989, Pages 281–282, https://doi.org/10.1093/comjnl/32.3.281

        Type Parameters:
        T - type of the list elements
        Parameters:
        list - list to partition
        Returns:
        stream of partitions of the list, each partition is an array or parts and each part is a list of elements
        Since:
        2.2
      • permutations

        public static <T> Stream<List<T>> permutations​(List<T> list)
        Generate a stream of permutations of a list.

        This method implements the Steinhaus–Johnson–Trotter algorithm with Even's speedup Steinhaus–Johnson–Trotter algorithm

        Type Parameters:
        T - type of the list elements
        Parameters:
        list - list to permute
        Returns:
        stream of permutations of the list
        Since:
        2.2