MATH-1416: Deleted code ported to "Commons Numbers" (module "commons-numbers-combinatorics").
Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/494745fd Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/494745fd Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/494745fd Branch: refs/heads/master Commit: 494745fdd0fb1c1a6cb7b955c42a8b6d956bd945 Parents: d442a77 Author: Gilles <er...@apache.org> Authored: Mon May 22 00:56:14 2017 +0200 Committer: Gilles <er...@apache.org> Committed: Mon May 22 00:56:14 2017 +0200 ---------------------------------------------------------------------- .../apache/commons/math4/util/Combinations.java | 415 ------------------ .../commons/math4/util/CombinatoricsUtils.java | 436 +------------------ .../commons/math4/util/CombinationsTest.java | 200 --------- .../math4/util/CombinatoricsUtilsTest.java | 283 +----------- .../commons/math4/util/FactorialLogTest.java | 111 ----- 5 files changed, 7 insertions(+), 1438 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/commons-math/blob/494745fd/src/main/java/org/apache/commons/math4/util/Combinations.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math4/util/Combinations.java b/src/main/java/org/apache/commons/math4/util/Combinations.java deleted file mode 100644 index b67e50c..0000000 --- a/src/main/java/org/apache/commons/math4/util/Combinations.java +++ /dev/null @@ -1,415 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math4.util; - -import java.io.Serializable; -import java.util.Arrays; -import java.util.Comparator; -import java.util.Iterator; -import java.util.NoSuchElementException; - -import org.apache.commons.numbers.core.ArithmeticUtils; -import org.apache.commons.math4.exception.DimensionMismatchException; -import org.apache.commons.math4.exception.MathInternalError; -import org.apache.commons.math4.exception.OutOfRangeException; - -/** - * Utility to create <a href="http://en.wikipedia.org/wiki/Combination"> - * combinations</a> {@code (n, k)} of {@code k} elements in a set of - * {@code n} elements. - * - * @since 3.3 - */ -public class Combinations implements Iterable<int[]> { - /** Size of the set from which combinations are drawn. */ - private final int n; - /** Number of elements in each combination. */ - private final int k; - /** Iteration order. */ - private final IterationOrder iterationOrder; - - /** - * Describes the type of iteration performed by the - * {@link #iterator() iterator}. - */ - private enum IterationOrder { - /** Lexicographic order. */ - LEXICOGRAPHIC - } - - /** - * Creates an instance whose range is the k-element subsets of - * {0, ..., n - 1} represented as {@code int[]} arrays. - * <p> - * The iteration order is lexicographic: the arrays returned by the - * {@link #iterator() iterator} are sorted in descending order and - * they are visited in lexicographic order with significance from - * right to left. - * For example, {@code new Combinations(4, 2).iterator()} returns - * an iterator that will generate the following sequence of arrays - * on successive calls to - * {@code next()}:<br> - * {@code [0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]} - * </p> - * If {@code k == 0} an iterator containing an empty array is returned; - * if {@code k == n} an iterator containing [0, ..., n - 1] is returned. - * - * @param n Size of the set from which subsets are selected. - * @param k Size of the subsets to be enumerated. - * @throws org.apache.commons.math4.exception.NotPositiveException if {@code n < 0}. - * @throws org.apache.commons.math4.exception.NumberIsTooLargeException if {@code k > n}. - */ - public Combinations(int n, - int k) { - this(n, k, IterationOrder.LEXICOGRAPHIC); - } - - /** - * Creates an instance whose range is the k-element subsets of - * {0, ..., n - 1} represented as {@code int[]} arrays. - * <p> - * If the {@code iterationOrder} argument is set to - * {@link IterationOrder#LEXICOGRAPHIC}, the arrays returned by the - * {@link #iterator() iterator} are sorted in descending order and - * they are visited in lexicographic order with significance from - * right to left. - * For example, {@code new Combinations(4, 2).iterator()} returns - * an iterator that will generate the following sequence of arrays - * on successive calls to - * {@code next()}:<br> - * {@code [0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]} - * </p> - * If {@code k == 0} an iterator containing an empty array is returned; - * if {@code k == n} an iterator containing [0, ..., n - 1] is returned. - * - * @param n Size of the set from which subsets are selected. - * @param k Size of the subsets to be enumerated. - * @param iterationOrder Specifies the {@link #iterator() iteration order}. - * @throws org.apache.commons.math4.exception.NotPositiveException if {@code n < 0}. - * @throws org.apache.commons.math4.exception.NumberIsTooLargeException if {@code k > n}. - */ - private Combinations(int n, - int k, - IterationOrder iterationOrder) { - CombinatoricsUtils.checkBinomial(n, k); - this.n = n; - this.k = k; - this.iterationOrder = iterationOrder; - } - - /** - * Gets the size of the set from which combinations are drawn. - * - * @return the size of the universe. - */ - public int getN() { - return n; - } - - /** - * Gets the number of elements in each combination. - * - * @return the size of the subsets to be enumerated. - */ - public int getK() { - return k; - } - - /** {@inheritDoc} */ - @Override - public Iterator<int[]> iterator() { - if (k == 0 || - k == n) { - return new SingletonIterator(MathArrays.natural(k)); - } - - switch (iterationOrder) { - case LEXICOGRAPHIC: - return new LexicographicIterator(n, k); - default: - throw new MathInternalError(); // Should never happen. - } - } - - /** - * Defines a lexicographic ordering of combinations. - * The returned comparator allows to compare any two combinations - * that can be produced by this instance's {@link #iterator() iterator}. - * Its {@code compare(int[],int[])} method will throw exceptions if - * passed combinations that are inconsistent with this instance: - * <ul> - * <li>{@code DimensionMismatchException} if the array lengths are not - * equal to {@code k},</li> - * <li>{@code OutOfRangeException} if an element of the array is not - * within the interval [0, {@code n}).</li> - * </ul> - * @return a lexicographic comparator. - */ - public Comparator<int[]> comparator() { - return new LexicographicComparator(n, k); - } - - /** - * Lexicographic combinations iterator. - * <p> - * Implementation follows Algorithm T in <i>The Art of Computer Programming</i> - * Internet Draft (PRE-FASCICLE 3A), "A Draft of Section 7.2.1.3 Generating All - * Combinations</a>, D. Knuth, 2004.</p> - * <p> - * The degenerate cases {@code k == 0} and {@code k == n} are NOT handled by this - * implementation. If constructor arguments satisfy {@code k == 0} - * or {@code k >= n}, no exception is generated, but the iterator is empty. - * </p> - * - */ - private static class LexicographicIterator implements Iterator<int[]> { - /** Size of subsets returned by the iterator */ - private final int k; - - /** - * c[1], ..., c[k] stores the next combination; c[k + 1], c[k + 2] are - * sentinels. - * <p> - * Note that c[0] is "wasted" but this makes it a little easier to - * follow the code. - * </p> - */ - private final int[] c; - - /** Return value for {@link #hasNext()} */ - private boolean more = true; - - /** Marker: smallest index such that c[j + 1] > j */ - private int j; - - /** - * Construct a CombinationIterator to enumerate k-sets from n. - * <p> - * NOTE: If {@code k === 0} or {@code k >= n}, the Iterator will be empty - * (that is, {@link #hasNext()} will return {@code false} immediately. - * </p> - * - * @param n size of the set from which subsets are enumerated - * @param k size of the subsets to enumerate - */ - LexicographicIterator(int n, int k) { - this.k = k; - c = new int[k + 3]; - if (k == 0 || k >= n) { - more = false; - return; - } - // Initialize c to start with lexicographically first k-set - for (int i = 1; i <= k; i++) { - c[i] = i - 1; - } - // Initialize sentinels - c[k + 1] = n; - c[k + 2] = 0; - j = k; // Set up invariant: j is smallest index such that c[j + 1] > j - } - - /** - * {@inheritDoc} - */ - @Override - public boolean hasNext() { - return more; - } - - /** - * {@inheritDoc} - */ - @Override - public int[] next() { - if (!more) { - throw new NoSuchElementException(); - } - // Copy return value (prepared by last activation) - final int[] ret = new int[k]; - System.arraycopy(c, 1, ret, 0, k); - - // Prepare next iteration - // T2 and T6 loop - int x = 0; - if (j > 0) { - x = j; - c[j] = x; - j--; - return ret; - } - // T3 - if (c[1] + 1 < c[2]) { - c[1]++; - return ret; - } else { - j = 2; - } - // T4 - boolean stepDone = false; - while (!stepDone) { - c[j - 1] = j - 2; - x = c[j] + 1; - if (x == c[j + 1]) { - j++; - } else { - stepDone = true; - } - } - // T5 - if (j > k) { - more = false; - return ret; - } - // T6 - c[j] = x; - j--; - return ret; - } - - /** - * Not supported. - */ - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - } - - /** - * Iterator with just one element to handle degenerate cases (full array, - * empty array) for combination iterator. - */ - private static class SingletonIterator implements Iterator<int[]> { - /** Singleton array */ - private final int[] singleton; - /** True on initialization, false after first call to next */ - private boolean more = true; - /** - * Create a singleton iterator providing the given array. - * @param singleton array returned by the iterator - */ - SingletonIterator(final int[] singleton) { - this.singleton = singleton; - } - /** @return True until next is called the first time, then false */ - @Override - public boolean hasNext() { - return more; - } - /** @return the singleton in first activation; throws NSEE thereafter */ - @Override - public int[] next() { - if (more) { - more = false; - return singleton; - } else { - throw new NoSuchElementException(); - } - } - /** Not supported */ - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - } - - /** - * Defines the lexicographic ordering of combinations, using - * the {@link #lexNorm(int[])} method. - */ - private static class LexicographicComparator - implements Comparator<int[]>, Serializable { - /** Serializable version identifier. */ - private static final long serialVersionUID = 20130906L; - /** Size of the set from which combinations are drawn. */ - private final int n; - /** Number of elements in each combination. */ - private final int k; - - /** - * @param n Size of the set from which subsets are selected. - * @param k Size of the subsets to be enumerated. - */ - LexicographicComparator(int n, int k) { - this.n = n; - this.k = k; - } - - /** - * {@inheritDoc} - * - * @throws DimensionMismatchException if the array lengths are not - * equal to {@code k}. - * @throws OutOfRangeException if an element of the array is not - * within the interval [0, {@code n}). - */ - @Override - public int compare(int[] c1, - int[] c2) { - if (c1.length != k) { - throw new DimensionMismatchException(c1.length, k); - } - if (c2.length != k) { - throw new DimensionMismatchException(c2.length, k); - } - - // Method "lexNorm" works with ordered arrays. - final int[] c1s = MathArrays.copyOf(c1); - Arrays.sort(c1s); - final int[] c2s = MathArrays.copyOf(c2); - Arrays.sort(c2s); - - final long v1 = lexNorm(c1s); - final long v2 = lexNorm(c2s); - - if (v1 < v2) { - return -1; - } else if (v1 > v2) { - return 1; - } else { - return 0; - } - } - - /** - * Computes the value (in base 10) represented by the digit - * (interpreted in base {@code n}) in the input array in reverse - * order. - * For example if {@code c} is {@code {3, 2, 1}}, and {@code n} - * is 3, the method will return 18. - * - * @param c Input array. - * @return the lexicographic norm. - * @throws OutOfRangeException if an element of the array is not - * within the interval [0, {@code n}). - */ - private long lexNorm(int[] c) { - long ret = 0; - for (int i = 0; i < c.length; i++) { - final int digit = c[i]; - if (digit < 0 || - digit >= n) { - throw new OutOfRangeException(digit, 0, n - 1); - } - - ret += c[i] * ArithmeticUtils.pow(n, i); - } - return ret; - } - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/494745fd/src/main/java/org/apache/commons/math4/util/CombinatoricsUtils.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math4/util/CombinatoricsUtils.java b/src/main/java/org/apache/commons/math4/util/CombinatoricsUtils.java index dcb7aa9..a4e227d 100644 --- a/src/main/java/org/apache/commons/math4/util/CombinatoricsUtils.java +++ b/src/main/java/org/apache/commons/math4/util/CombinatoricsUtils.java @@ -25,6 +25,8 @@ import org.apache.commons.math4.exception.NotPositiveException; import org.apache.commons.math4.exception.NumberIsTooLargeException; import org.apache.commons.math4.exception.util.LocalizedFormats; import org.apache.commons.numbers.gamma.LogGamma; +import org.apache.commons.numbers.combinatorics.Factorial; +import org.apache.commons.numbers.combinatorics.BinomialCoefficient; /** * Combinatorial utilities. @@ -32,302 +34,12 @@ import org.apache.commons.numbers.gamma.LogGamma; * @since 3.3 */ public final class CombinatoricsUtils { - - /** All long-representable factorials */ - static final long[] FACTORIALS = new long[] { - 1l, 1l, 2l, - 6l, 24l, 120l, - 720l, 5040l, 40320l, - 362880l, 3628800l, 39916800l, - 479001600l, 6227020800l, 87178291200l, - 1307674368000l, 20922789888000l, 355687428096000l, - 6402373705728000l, 121645100408832000l, 2432902008176640000l }; - /** Stirling numbers of the second kind. */ static final AtomicReference<long[][]> STIRLING_S2 = new AtomicReference<> (null); - /** - * Default implementation of {@link #factorialLog(int)} method: - * <ul> - * <li>No pre-computation</li> - * <li>No cache allocation</li> - * </ul> - */ - private static final FactorialLog FACTORIAL_LOG_NO_CACHE = FactorialLog.create(); - /** Private constructor (class contains only static methods). */ private CombinatoricsUtils() {} - - /** - * Returns an exact representation of the <a - * href="http://mathworld.wolfram.com/BinomialCoefficient.html"> Binomial - * Coefficient</a>, "{@code n choose k}", the number of - * {@code k}-element subsets that can be selected from an - * {@code n}-element set. - * <p> - * <Strong>Preconditions</strong>: - * <ul> - * <li> {@code 0 <= k <= n } (otherwise - * {@code MathIllegalArgumentException} is thrown)</li> - * <li> The result is small enough to fit into a {@code long}. The - * largest value of {@code n} for which all coefficients are - * {@code < Long.MAX_VALUE} is 66. If the computed value exceeds - * {@code Long.MAX_VALUE} a {@code MathArithMeticException} is - * thrown.</li> - * </ul> - * - * @param n the size of the set - * @param k the size of the subsets to be counted - * @return {@code n choose k} - * @throws NotPositiveException if {@code n < 0}. - * @throws NumberIsTooLargeException if {@code k > n}. - * @throws MathArithmeticException if the result is too large to be - * represented by a long integer. - */ - public static long binomialCoefficient(final int n, final int k) - throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException { - CombinatoricsUtils.checkBinomial(n, k); - if ((n == k) || (k == 0)) { - return 1; - } - if ((k == 1) || (k == n - 1)) { - return n; - } - // Use symmetry for large k - if (k > n / 2) { - return binomialCoefficient(n, n - k); - } - - // We use the formula - // (n choose k) = n! / (n-k)! / k! - // (n choose k) == ((n-k+1)*...*n) / (1*...*k) - // which could be written - // (n choose k) == (n-1 choose k-1) * n / k - long result = 1; - if (n <= 61) { - // For n <= 61, the naive implementation cannot overflow. - int i = n - k + 1; - for (int j = 1; j <= k; j++) { - result = result * i / j; - i++; - } - } else if (n <= 66) { - // For n > 61 but n <= 66, the result cannot overflow, - // but we must take care not to overflow intermediate values. - int i = n - k + 1; - for (int j = 1; j <= k; j++) { - // We know that (result * i) is divisible by j, - // but (result * i) may overflow, so we split j: - // Filter out the gcd, d, so j/d and i/d are integer. - // result is divisible by (j/d) because (j/d) - // is relative prime to (i/d) and is a divisor of - // result * (i/d). - final long d = ArithmeticUtils.gcd(i, j); - result = (result / (j / d)) * (i / d); - i++; - } - } else { - // For n > 66, a result overflow might occur, so we check - // the multiplication, taking care to not overflow - // unnecessary. - int i = n - k + 1; - for (int j = 1; j <= k; j++) { - final long d = ArithmeticUtils.gcd(i, j); - result = ArithmeticUtils.mulAndCheck(result / (j / d), i / d); - i++; - } - } - return result; - } - - /** - * Returns a {@code double} representation of the <a - * href="http://mathworld.wolfram.com/BinomialCoefficient.html"> Binomial - * Coefficient</a>, "{@code n choose k}", the number of - * {@code k}-element subsets that can be selected from an - * {@code n}-element set. - * <p> - * <Strong>Preconditions</strong>: - * <ul> - * <li> {@code 0 <= k <= n } (otherwise - * {@code IllegalArgumentException} is thrown)</li> - * <li> The result is small enough to fit into a {@code double}. The - * largest value of {@code n} for which all coefficients are < - * Double.MAX_VALUE is 1029. If the computed value exceeds Double.MAX_VALUE, - * Double.POSITIVE_INFINITY is returned</li> - * </ul> - * - * @param n the size of the set - * @param k the size of the subsets to be counted - * @return {@code n choose k} - * @throws NotPositiveException if {@code n < 0}. - * @throws NumberIsTooLargeException if {@code k > n}. - * @throws MathArithmeticException if the result is too large to be - * represented by a long integer. - */ - public static double binomialCoefficientDouble(final int n, final int k) - throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException { - CombinatoricsUtils.checkBinomial(n, k); - if ((n == k) || (k == 0)) { - return 1d; - } - if ((k == 1) || (k == n - 1)) { - return n; - } - if (k > n/2) { - return binomialCoefficientDouble(n, n - k); - } - if (n < 67) { - return binomialCoefficient(n,k); - } - - double result = 1d; - for (int i = 1; i <= k; i++) { - result *= (double)(n - k + i) / (double)i; - } - - return FastMath.floor(result + 0.5); - } - - /** - * Returns the natural {@code log} of the <a - * href="http://mathworld.wolfram.com/BinomialCoefficient.html"> Binomial - * Coefficient</a>, "{@code n choose k}", the number of - * {@code k}-element subsets that can be selected from an - * {@code n}-element set. - * <p> - * <Strong>Preconditions</strong>: - * <ul> - * <li> {@code 0 <= k <= n } (otherwise - * {@code MathIllegalArgumentException} is thrown)</li> - * </ul> - * - * @param n the size of the set - * @param k the size of the subsets to be counted - * @return {@code n choose k} - * @throws NotPositiveException if {@code n < 0}. - * @throws NumberIsTooLargeException if {@code k > n}. - * @throws MathArithmeticException if the result is too large to be - * represented by a long integer. - */ - public static double binomialCoefficientLog(final int n, final int k) - throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException { - CombinatoricsUtils.checkBinomial(n, k); - if ((n == k) || (k == 0)) { - return 0; - } - if ((k == 1) || (k == n - 1)) { - return FastMath.log(n); - } - - /* - * For values small enough to do exact integer computation, - * return the log of the exact value - */ - if (n < 67) { - return FastMath.log(binomialCoefficient(n,k)); - } - - /* - * Return the log of binomialCoefficientDouble for values that will not - * overflow binomialCoefficientDouble - */ - if (n < 1030) { - return FastMath.log(binomialCoefficientDouble(n, k)); - } - - if (k > n / 2) { - return binomialCoefficientLog(n, n - k); - } - - /* - * Sum logs for values that could overflow - */ - double logSum = 0; - - // n!/(n-k)! - for (int i = n - k + 1; i <= n; i++) { - logSum += FastMath.log(i); - } - - // divide by k! - for (int i = 2; i <= k; i++) { - logSum -= FastMath.log(i); - } - - return logSum; - } - - /** - * Returns n!. Shorthand for {@code n} <a - * href="http://mathworld.wolfram.com/Factorial.html"> Factorial</a>, the - * product of the numbers {@code 1,...,n}. - * <p> - * <Strong>Preconditions</strong>: - * <ul> - * <li> {@code n >= 0} (otherwise - * {@code MathIllegalArgumentException} is thrown)</li> - * <li> The result is small enough to fit into a {@code long}. The - * largest value of {@code n} for which {@code n!} does not exceed - * Long.MAX_VALUE} is 20. If the computed value exceeds {@code Long.MAX_VALUE} - * an {@code MathArithMeticException } is thrown.</li> - * </ul> - * - * @param n argument - * @return {@code n!} - * @throws MathArithmeticException if the result is too large to be represented - * by a {@code long}. - * @throws NotPositiveException if {@code n < 0}. - * @throws MathArithmeticException if {@code n > 20}: The factorial value is too - * large to fit in a {@code long}. - */ - public static long factorial(final int n) throws NotPositiveException, MathArithmeticException { - if (n < 0) { - throw new NotPositiveException(LocalizedFormats.FACTORIAL_NEGATIVE_PARAMETER, - n); - } - if (n > 20) { - throw new MathArithmeticException(); - } - return FACTORIALS[n]; - } - - /** - * Compute n!, the<a href="http://mathworld.wolfram.com/Factorial.html"> - * factorial</a> of {@code n} (the product of the numbers 1 to n), as a - * {@code double}. - * The result should be small enough to fit into a {@code double}: The - * largest {@code n} for which {@code n!} does not exceed - * {@code Double.MAX_VALUE} is 170. If the computed value exceeds - * {@code Double.MAX_VALUE}, {@code Double.POSITIVE_INFINITY} is returned. - * - * @param n Argument. - * @return {@code n!} - * @throws NotPositiveException if {@code n < 0}. - */ - public static double factorialDouble(final int n) throws NotPositiveException { - if (n < 0) { - throw new NotPositiveException(LocalizedFormats.FACTORIAL_NEGATIVE_PARAMETER, - n); - } - if (n < 21) { - return FACTORIALS[n]; - } - return FastMath.floor(FastMath.exp(CombinatoricsUtils.factorialLog(n)) + 0.5); - } - - /** - * Compute the natural logarithm of the factorial of {@code n}. - * - * @param n Argument. - * @return {@code log(n!)} - * @throws NotPositiveException if {@code n < 0}. - */ - public static double factorialLog(final int n) throws NotPositiveException { - return FACTORIAL_LOG_NO_CACHE.value(n); - } - /** * Returns the <a * href="http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html"> @@ -394,160 +106,22 @@ public final class CombinatoricsUtils { } else if (k == 2) { return (1l << (n - 1)) - 1l; } else if (k == n - 1) { - return binomialCoefficient(n, 2); + return BinomialCoefficient.value(n, 2); } else { // definition formula: note that this may trigger some overflow long sum = 0; long sign = ((k & 0x1) == 0) ? 1 : -1; for (int j = 1; j <= k; ++j) { sign = -sign; - sum += sign * binomialCoefficient(k, j) * ArithmeticUtils.pow(j, n); + sum += sign * BinomialCoefficient.value(k, j) * ArithmeticUtils.pow(j, n); if (sum < 0) { // there was an overflow somewhere throw new MathArithmeticException(LocalizedFormats.ARGUMENT_OUTSIDE_DOMAIN, n, 0, stirlingS2.length - 1); } } - return sum / factorial(k); - } - } - - } - - /** - * Returns an iterator whose range is the k-element subsets of {0, ..., n - 1} - * represented as {@code int[]} arrays. - * <p> - * 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 - * {@code next()}:</p><p> - * {@code [0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]} - * </p><p> - * If {@code k == 0} an Iterator containing an empty array is returned and - * if {@code k == n} an Iterator containing [0, ..., n -1] is returned.</p> - * - * @param n Size of the set from which subsets are selected. - * @param k Size of the subsets to be enumerated. - * @return an {@link Iterator iterator} over the k-sets in n. - * @throws NotPositiveException if {@code n < 0}. - * @throws NumberIsTooLargeException if {@code k > n}. - */ - public static Iterator<int[]> combinationsIterator(int n, int k) { - return new Combinations(n, k).iterator(); - } - - /** - * Check binomial preconditions. - * - * @param n Size of the set. - * @param k Size of the subsets to be counted. - * @throws NotPositiveException if {@code n < 0}. - * @throws NumberIsTooLargeException if {@code k > n}. - */ - public static void checkBinomial(final int n, - final int k) - throws NumberIsTooLargeException, - NotPositiveException { - if (n < k) { - throw new NumberIsTooLargeException(LocalizedFormats.BINOMIAL_INVALID_PARAMETERS_ORDER, - k, n, true); - } - if (n < 0) { - throw new NotPositiveException(LocalizedFormats.BINOMIAL_NEGATIVE_PARAMETER, n); - } - } - - /** - * Class for computing the natural logarithm of the factorial of {@code n}. - * It allows to allocate a cache of precomputed values. - * In case of cache miss, computation is performed by a call to - * {@link LogGamma#value(double)}. - */ - public static final class FactorialLog { - /** - * Precomputed values of the function: - * {@code LOG_FACTORIALS[i] = log(i!)}. - */ - private final double[] LOG_FACTORIALS; - - /** - * Creates an instance, reusing the already computed values if available. - * - * @param numValues Number of values of the function to compute. - * @param cache Existing cache. - * @throw NotPositiveException if {@code n < 0}. - */ - private FactorialLog(int numValues, - double[] cache) { - if (numValues < 0) { - throw new NotPositiveException(numValues); - } - - LOG_FACTORIALS = new double[numValues]; - - final int beginCopy = 2; - final int endCopy = cache == null || cache.length <= beginCopy ? - beginCopy : cache.length <= numValues ? - cache.length : numValues; - - // Copy available values. - for (int i = beginCopy; i < endCopy; i++) { - LOG_FACTORIALS[i] = cache[i]; + return sum / Factorial.value(k); } - - // Precompute. - for (int i = endCopy; i < numValues; i++) { - LOG_FACTORIALS[i] = LOG_FACTORIALS[i - 1] + FastMath.log(i); - } - } - - /** - * Creates an instance with no precomputed values. - * @return instance with no precomputed values - */ - public static FactorialLog create() { - return new FactorialLog(0, null); - } - - /** - * Creates an instance with the specified cache size. - * - * @param cacheSize Number of precomputed values of the function. - * @return a new instance where {@code cacheSize} values have been - * precomputed. - * @throws NotPositiveException if {@code n < 0}. - */ - public FactorialLog withCache(final int cacheSize) { - return new FactorialLog(cacheSize, LOG_FACTORIALS); - } - - /** - * Computes {@code log(n!)}. - * - * @param n Argument. - * @return {@code log(n!)}. - * @throws NotPositiveException if {@code n < 0}. - */ - public double value(final int n) { - if (n < 0) { - throw new NotPositiveException(LocalizedFormats.FACTORIAL_NEGATIVE_PARAMETER, - n); - } - - // Use cache of precomputed values. - if (n < LOG_FACTORIALS.length) { - return LOG_FACTORIALS[n]; - } - - // Use cache of precomputed factorial values. - if (n < FACTORIALS.length) { - return FastMath.log(FACTORIALS[n]); - } - - // Delegate. - return LogGamma.value(n + 1); } } } http://git-wip-us.apache.org/repos/asf/commons-math/blob/494745fd/src/test/java/org/apache/commons/math4/util/CombinationsTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/commons/math4/util/CombinationsTest.java b/src/test/java/org/apache/commons/math4/util/CombinationsTest.java deleted file mode 100644 index a2b0c4b..0000000 --- a/src/test/java/org/apache/commons/math4/util/CombinationsTest.java +++ /dev/null @@ -1,200 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math4.util; - -import java.util.Iterator; -import java.util.Comparator; - -import org.apache.commons.math4.exception.DimensionMismatchException; -import org.apache.commons.math4.exception.MathIllegalArgumentException; -import org.apache.commons.math4.exception.OutOfRangeException; -import org.apache.commons.math4.util.Combinations; -import org.apache.commons.math4.util.CombinatoricsUtils; -import org.junit.Assert; -import org.junit.Test; - -/** - * Tests for the {@link Combinations} class. - * - */ -public class CombinationsTest { - @Test - public void testAccessor1() { - final int n = 5; - final int k = 3; - Assert.assertEquals(n, new Combinations(n, k).getN()); - } - @Test - public void testAccessor2() { - final int n = 5; - final int k = 3; - Assert.assertEquals(k, new Combinations(n, k).getK()); - } - - @Test - public void testLexicographicIterator() { - checkLexicographicIterator(new Combinations(5, 3)); - checkLexicographicIterator(new Combinations(6, 4)); - checkLexicographicIterator(new Combinations(8, 2)); - checkLexicographicIterator(new Combinations(6, 1)); - checkLexicographicIterator(new Combinations(3, 3)); - checkLexicographicIterator(new Combinations(1, 1)); - checkLexicographicIterator(new Combinations(1, 0)); - checkLexicographicIterator(new Combinations(0, 0)); - checkLexicographicIterator(new Combinations(4, 2)); - checkLexicographicIterator(new Combinations(123, 2)); - } - - @Test(expected=DimensionMismatchException.class) - public void testLexicographicComparatorWrongIterate1() { - final int n = 5; - final int k = 3; - final Comparator<int[]> comp = new Combinations(n, k).comparator(); - comp.compare(new int[] {1}, new int[] {0, 1, 2}); - } - - @Test(expected=DimensionMismatchException.class) - public void testLexicographicComparatorWrongIterate2() { - final int n = 5; - final int k = 3; - final Comparator<int[]> comp = new Combinations(n, k).comparator(); - comp.compare(new int[] {0, 1, 2}, new int[] {0, 1, 2, 3}); - } - - @Test(expected=OutOfRangeException.class) - public void testLexicographicComparatorWrongIterate3() { - final int n = 5; - final int k = 3; - final Comparator<int[]> comp = new Combinations(n, k).comparator(); - comp.compare(new int[] {1, 2, 5}, new int[] {0, 1, 2}); - } - - @Test(expected=OutOfRangeException.class) - public void testLexicographicComparatorWrongIterate4() { - final int n = 5; - final int k = 3; - final Comparator<int[]> comp = new Combinations(n, k).comparator(); - comp.compare(new int[] {1, 2, 4}, new int[] {-1, 1, 2}); - } - - @Test - public void testLexicographicComparator() { - final int n = 5; - final int k = 3; - final Comparator<int[]> comp = new Combinations(n, k).comparator(); - Assert.assertEquals(1, comp.compare(new int[] {1, 2, 4}, - new int[] {1, 2, 3})); - Assert.assertEquals(-1, comp.compare(new int[] {0, 1, 4}, - new int[] {0, 2, 4})); - Assert.assertEquals(0, comp.compare(new int[] {1, 3, 4}, - new int[] {1, 3, 4})); - } - - /** - * Check that iterates can be passed unsorted. - */ - @Test - public void testLexicographicComparatorUnsorted() { - final int n = 5; - final int k = 3; - final Comparator<int[]> comp = new Combinations(n, k).comparator(); - Assert.assertEquals(1, comp.compare(new int[] {1, 4, 2}, - new int[] {1, 3, 2})); - Assert.assertEquals(-1, comp.compare(new int[] {0, 4, 1}, - new int[] {0, 4, 2})); - Assert.assertEquals(0, comp.compare(new int[] {1, 4, 3}, - new int[] {1, 3, 4})); - } - - @Test - public void testEmptyCombination() { - final Iterator<int[]> iter = new Combinations(12345, 0).iterator(); - Assert.assertTrue(iter.hasNext()); - final int[] c = iter.next(); - Assert.assertEquals(0, c.length); - Assert.assertFalse(iter.hasNext()); - } - - @Test - public void testFullSetCombination() { - final int n = 67; - final Iterator<int[]> iter = new Combinations(n, n).iterator(); - Assert.assertTrue(iter.hasNext()); - final int[] c = iter.next(); - Assert.assertEquals(n, c.length); - - for (int i = 0; i < n; i++) { - Assert.assertEquals(i, c[i]); - } - - Assert.assertFalse(iter.hasNext()); - } - - /** - * Verifies that the iterator generates a lexicographically - * increasing sequence of b(n,k) arrays, each having length k - * and each array itself increasing. - * - * @param c Combinations. - */ - private void checkLexicographicIterator(Combinations c) { - final Comparator<int[]> comp = c.comparator(); - final int n = c.getN(); - final int k = c.getK(); - - int[] lastIterate = null; - - long numIterates = 0; - for (int[] iterate : c) { - Assert.assertEquals(k, iterate.length); - - // Check that the sequence of iterates is ordered. - if (lastIterate != null) { - Assert.assertTrue(comp.compare(iterate, lastIterate) == 1); - } - - // Check that each iterate is ordered. - for (int i = 1; i < iterate.length; i++) { - Assert.assertTrue(iterate[i] > iterate[i - 1]); - } - - lastIterate = iterate; - ++numIterates; - } - - // Check the number of iterates. - Assert.assertEquals(CombinatoricsUtils.binomialCoefficient(n, k), - numIterates); - } - - @Test - public void testCombinationsIteratorFail() { - try { - new Combinations(4, 5).iterator(); - Assert.fail("expecting MathIllegalArgumentException"); - } catch (MathIllegalArgumentException ex) { - // ignored - } - - try { - new Combinations(-1, -2).iterator(); - Assert.fail("expecting MathIllegalArgumentException"); - } catch (MathIllegalArgumentException ex) { - // ignored - } - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/494745fd/src/test/java/org/apache/commons/math4/util/CombinatoricsUtilsTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/commons/math4/util/CombinatoricsUtilsTest.java b/src/test/java/org/apache/commons/math4/util/CombinatoricsUtilsTest.java index b3798d5..43a0e9f 100644 --- a/src/test/java/org/apache/commons/math4/util/CombinatoricsUtilsTest.java +++ b/src/test/java/org/apache/commons/math4/util/CombinatoricsUtilsTest.java @@ -26,6 +26,7 @@ import org.apache.commons.math4.exception.MathIllegalArgumentException; import org.apache.commons.math4.exception.NotPositiveException; import org.apache.commons.math4.exception.NumberIsTooLargeException; import org.apache.commons.numbers.core.ArithmeticUtils; +import org.apache.commons.numbers.combinatorics.BinomialCoefficient; import org.apache.commons.math4.util.CombinatoricsUtils; import org.apache.commons.math4.util.FastMath; import org.junit.Assert; @@ -40,221 +41,6 @@ public class CombinatoricsUtilsTest { /** cached binomial coefficients */ private static final List<Map<Integer, Long>> binomialCache = new ArrayList<>(); - /** Verify that b(0,0) = 1 */ - @Test - public void test0Choose0() { - Assert.assertEquals(CombinatoricsUtils.binomialCoefficientDouble(0, 0), 1d, 0); - Assert.assertEquals(CombinatoricsUtils.binomialCoefficientLog(0, 0), 0d, 0); - Assert.assertEquals(CombinatoricsUtils.binomialCoefficient(0, 0), 1); - } - - @Test - public void testBinomialCoefficient() { - long[] bcoef5 = { - 1, - 5, - 10, - 10, - 5, - 1 }; - long[] bcoef6 = { - 1, - 6, - 15, - 20, - 15, - 6, - 1 }; - for (int i = 0; i < 6; i++) { - Assert.assertEquals("5 choose " + i, bcoef5[i], CombinatoricsUtils.binomialCoefficient(5, i)); - } - for (int i = 0; i < 7; i++) { - Assert.assertEquals("6 choose " + i, bcoef6[i], CombinatoricsUtils.binomialCoefficient(6, i)); - } - - for (int n = 1; n < 10; n++) { - for (int k = 0; k <= n; k++) { - Assert.assertEquals(n + " choose " + k, binomialCoefficient(n, k), CombinatoricsUtils.binomialCoefficient(n, k)); - Assert.assertEquals(n + " choose " + k, binomialCoefficient(n, k), CombinatoricsUtils.binomialCoefficientDouble(n, k), Double.MIN_VALUE); - Assert.assertEquals(n + " choose " + k, FastMath.log(binomialCoefficient(n, k)), CombinatoricsUtils.binomialCoefficientLog(n, k), 10E-12); - } - } - - int[] n = { 34, 66, 100, 1500, 1500 }; - int[] k = { 17, 33, 10, 1500 - 4, 4 }; - for (int i = 0; i < n.length; i++) { - long expected = binomialCoefficient(n[i], k[i]); - Assert.assertEquals(n[i] + " choose " + k[i], expected, - CombinatoricsUtils.binomialCoefficient(n[i], k[i])); - Assert.assertEquals(n[i] + " choose " + k[i], expected, - CombinatoricsUtils.binomialCoefficientDouble(n[i], k[i]), 0.0); - Assert.assertEquals("log(" + n[i] + " choose " + k[i] + ")", FastMath.log(expected), - CombinatoricsUtils.binomialCoefficientLog(n[i], k[i]), 0.0); - } - } - - @Test - public void testBinomialCoefficientFail() { - try { - CombinatoricsUtils.binomialCoefficient(4, 5); - Assert.fail("expecting MathIllegalArgumentException"); - } catch (MathIllegalArgumentException ex) { - // ignored - } - - try { - CombinatoricsUtils.binomialCoefficientDouble(4, 5); - Assert.fail("expecting MathIllegalArgumentException"); - } catch (MathIllegalArgumentException ex) { - // ignored - } - - try { - CombinatoricsUtils.binomialCoefficientLog(4, 5); - Assert.fail("expecting MathIllegalArgumentException"); - } catch (MathIllegalArgumentException ex) { - // ignored - } - - try { - CombinatoricsUtils.binomialCoefficient(-1, -2); - Assert.fail("expecting MathIllegalArgumentException"); - } catch (MathIllegalArgumentException ex) { - // ignored - } - try { - CombinatoricsUtils.binomialCoefficientDouble(-1, -2); - Assert.fail("expecting MathIllegalArgumentException"); - } catch (MathIllegalArgumentException ex) { - // ignored - } - try { - CombinatoricsUtils.binomialCoefficientLog(-1, -2); - Assert.fail("expecting MathIllegalArgumentException"); - } catch (MathIllegalArgumentException ex) { - // ignored - } - - try { - CombinatoricsUtils.binomialCoefficient(67, 30); - Assert.fail("expecting ArithmeticException"); - } catch (ArithmeticException ex) { - // ignored - } - try { - CombinatoricsUtils.binomialCoefficient(67, 34); - Assert.fail("expecting ArithmeticException"); - } catch (ArithmeticException ex) { - // ignored - } - double x = CombinatoricsUtils.binomialCoefficientDouble(1030, 515); - Assert.assertTrue("expecting infinite binomial coefficient", Double - .isInfinite(x)); - } - - /** - * Tests correctness for large n and sharpness of upper bound in API doc - * JIRA: MATH-241 - */ - @Test - public void testBinomialCoefficientLarge() throws Exception { - // This tests all legal and illegal values for n <= 200. - for (int n = 0; n <= 200; n++) { - for (int k = 0; k <= n; k++) { - long ourResult = -1; - long exactResult = -1; - boolean shouldThrow = false; - boolean didThrow = false; - try { - ourResult = CombinatoricsUtils.binomialCoefficient(n, k); - } catch (ArithmeticException ex) { - didThrow = true; - } - try { - exactResult = binomialCoefficient(n, k); - } catch (ArithmeticException ex) { - shouldThrow = true; - } - Assert.assertEquals(n + " choose " + k, exactResult, ourResult); - Assert.assertEquals(n + " choose " + k, shouldThrow, didThrow); - Assert.assertTrue(n + " choose " + k, (n > 66 || !didThrow)); - - if (!shouldThrow && exactResult > 1) { - Assert.assertEquals(n + " choose " + k, 1., - CombinatoricsUtils.binomialCoefficientDouble(n, k) / exactResult, 1e-10); - Assert.assertEquals(n + " choose " + k, 1, - CombinatoricsUtils.binomialCoefficientLog(n, k) / FastMath.log(exactResult), 1e-10); - } - } - } - - long ourResult = CombinatoricsUtils.binomialCoefficient(300, 3); - long exactResult = binomialCoefficient(300, 3); - Assert.assertEquals(exactResult, ourResult); - - ourResult = CombinatoricsUtils.binomialCoefficient(700, 697); - exactResult = binomialCoefficient(700, 697); - Assert.assertEquals(exactResult, ourResult); - - // This one should throw - try { - CombinatoricsUtils.binomialCoefficient(700, 300); - Assert.fail("Expecting ArithmeticException"); - } catch (ArithmeticException ex) { - // Expected - } - - int n = 10000; - ourResult = CombinatoricsUtils.binomialCoefficient(n, 3); - exactResult = binomialCoefficient(n, 3); - Assert.assertEquals(exactResult, ourResult); - Assert.assertEquals(1, CombinatoricsUtils.binomialCoefficientDouble(n, 3) / exactResult, 1e-10); - Assert.assertEquals(1, CombinatoricsUtils.binomialCoefficientLog(n, 3) / FastMath.log(exactResult), 1e-10); - - } - - @Test - public void testFactorial() { - for (int i = 1; i < 21; i++) { - Assert.assertEquals(i + "! ", factorial(i), CombinatoricsUtils.factorial(i)); - Assert.assertEquals(i + "! ", factorial(i), CombinatoricsUtils.factorialDouble(i), Double.MIN_VALUE); - Assert.assertEquals(i + "! ", FastMath.log(factorial(i)), CombinatoricsUtils.factorialLog(i), 10E-12); - } - - Assert.assertEquals("0", 1, CombinatoricsUtils.factorial(0)); - Assert.assertEquals("0", 1.0d, CombinatoricsUtils.factorialDouble(0), 1E-14); - Assert.assertEquals("0", 0.0d, CombinatoricsUtils.factorialLog(0), 1E-14); - } - - @Test - public void testFactorialFail() { - try { - CombinatoricsUtils.factorial(-1); - Assert.fail("expecting MathIllegalArgumentException"); - } catch (MathIllegalArgumentException ex) { - // ignored - } - try { - CombinatoricsUtils.factorialDouble(-1); - Assert.fail("expecting MathIllegalArgumentException"); - } catch (MathIllegalArgumentException ex) { - // ignored - } - try { - CombinatoricsUtils.factorialLog(-1); - Assert.fail("expecting MathIllegalArgumentException"); - } catch (MathIllegalArgumentException ex) { - // ignored - } - try { - CombinatoricsUtils.factorial(21); - Assert.fail("expecting MathArithmeticException"); - } catch (MathArithmeticException ex) { - // ignored - } - Assert.assertTrue("expecting infinite factorial value", Double.isInfinite(CombinatoricsUtils.factorialDouble(171))); - } - @Test public void testStirlingS2() { @@ -265,7 +51,7 @@ public class CombinatoricsUtilsTest { Assert.assertEquals(1, CombinatoricsUtils.stirlingS2(n, 1)); if (n > 2) { Assert.assertEquals((1l << (n - 1)) - 1l, CombinatoricsUtils.stirlingS2(n, 2)); - Assert.assertEquals(CombinatoricsUtils.binomialCoefficient(n, 2), + Assert.assertEquals(BinomialCoefficient.value(n, 2), CombinatoricsUtils.stirlingS2(n, n - 1)); } Assert.assertEquals(1, CombinatoricsUtils.stirlingS2(n, n)); @@ -311,69 +97,4 @@ public class CombinatoricsUtilsTest { public void testStirlingS2Overflow() { CombinatoricsUtils.stirlingS2(26, 9); } - - @Test(expected=NotPositiveException.class) - public void testCheckBinomial1() { - // n < 0 - CombinatoricsUtils.checkBinomial(-1, -2); - } - - @Test(expected=NumberIsTooLargeException.class) - public void testCheckBinomial2() { - // k > n - CombinatoricsUtils.checkBinomial(4, 5); - } - - @Test - public void testCheckBinomial3() { - // OK (no exception thrown) - CombinatoricsUtils.checkBinomial(5, 4); - } - - /** - * Exact (caching) recursive implementation to test against - */ - private long binomialCoefficient(int n, int k) throws ArithmeticException { - if (binomialCache.size() > n) { - Long cachedResult = binomialCache.get(n).get(Integer.valueOf(k)); - if (cachedResult != null) { - return cachedResult.longValue(); - } - } - long result = -1; - if ((n == k) || (k == 0)) { - result = 1; - } else if ((k == 1) || (k == n - 1)) { - result = n; - } else { - // Reduce stack depth for larger values of n - if (k < n - 100) { - binomialCoefficient(n - 100, k); - } - if (k > 100) { - binomialCoefficient(n - 100, k - 100); - } - result = ArithmeticUtils.addAndCheck(binomialCoefficient(n - 1, k - 1), - binomialCoefficient(n - 1, k)); - } - if (result == -1) { - throw new ArithmeticException(); - } - for (int i = binomialCache.size(); i < n + 1; i++) { - binomialCache.add(new HashMap<Integer, Long>()); - } - binomialCache.get(n).put(Integer.valueOf(k), Long.valueOf(result)); - return result; - } - - /** - * Exact direct multiplication implementation to test against - */ - private long factorial(int n) { - long result = 1; - for (int i = 2; i <= n; i++) { - result *= i; - } - return result; - } } http://git-wip-us.apache.org/repos/asf/commons-math/blob/494745fd/src/test/java/org/apache/commons/math4/util/FactorialLogTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/commons/math4/util/FactorialLogTest.java b/src/test/java/org/apache/commons/math4/util/FactorialLogTest.java deleted file mode 100644 index 6e0c40f..0000000 --- a/src/test/java/org/apache/commons/math4/util/FactorialLogTest.java +++ /dev/null @@ -1,111 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math4.util; - -import org.apache.commons.math4.exception.NotPositiveException; -import org.apache.commons.numbers.gamma.LogGamma; - -import org.junit.Assert; -import org.junit.Test; - -/** - * Test cases for the {@link CombinatoricsUtils.FactorialLog} class. - */ -public class FactorialLogTest { - - @Test(expected=NotPositiveException.class) - public void testPrecondition1() { - CombinatoricsUtils.FactorialLog.create().withCache(-1); - } - - @Test(expected=NotPositiveException.class) - public void testNonPositiveArgument() { - final CombinatoricsUtils.FactorialLog f = CombinatoricsUtils.FactorialLog.create(); - f.value(-1); - } - - @Test - public void testDelegation() { - final CombinatoricsUtils.FactorialLog f = CombinatoricsUtils.FactorialLog.create(); - - // Starting at 21 because for smaller arguments, there is no delegation to the - // "LogGamma" class. - for (int i = 21; i < 10000; i++) { - final double expected = LogGamma.value(i + 1); - Assert.assertEquals(i + "! ", - expected, f.value(i), 0d); - } - } - - @Test - public void testCompareDirectWithoutCache() { - // This test shows that delegating to the "Gamma" class will also lead to a - // less accurate result. - - final int max = 100; - final CombinatoricsUtils.FactorialLog f = CombinatoricsUtils.FactorialLog.create(); - - for (int i = 0; i < max; i++) { - final double expected = factorialLog(i); - Assert.assertEquals(i + "! ", - expected, f.value(i), 2 * Math.ulp(expected)); - } - } - - @Test - public void testCompareDirectWithCache() { - final int max = 1000; - final CombinatoricsUtils.FactorialLog f = CombinatoricsUtils.FactorialLog.create().withCache(max); - - for (int i = 0; i < max; i++) { - final double expected = factorialLog(i); - Assert.assertEquals(i + "! ", - expected, f.value(i), 0d); - } - } - - @Test - public void testCacheIncrease() { - final int max = 100; - final CombinatoricsUtils.FactorialLog f1 = CombinatoricsUtils.FactorialLog.create().withCache(max); - final CombinatoricsUtils.FactorialLog f2 = f1.withCache(2 * max); - - final int val = max + max / 2; - final double expected = factorialLog(val); - Assert.assertEquals(expected, f2.value(val), 0d); - } - - @Test - public void testCacheDecrease() { - final int max = 100; - final CombinatoricsUtils.FactorialLog f1 = CombinatoricsUtils.FactorialLog.create().withCache(max); - final CombinatoricsUtils.FactorialLog f2 = f1.withCache(max / 2); - - final int val = max / 4; - final double expected = factorialLog(val); - Assert.assertEquals(expected, f2.value(val), 0d); - } - - // Direct implementation. - private double factorialLog(final int n) { - double logSum = 0; - for (int i = 2; i <= n; i++) { - logSum += FastMath.log(i); - } - return logSum; - } -}