You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2017/05/21 23:29:14 UTC
[3/6] [math] MATH-1416: Deleted code ported to "Commons Numbers"
(module "commons-numbers-combinatorics").
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;
- }
-}