Repository: commons-numbers Updated Branches: refs/heads/master 0ad65c010 -> 5b140a0e2
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/CombinationsTest.java ---------------------------------------------------------------------- diff --git a/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/CombinationsTest.java b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/CombinationsTest.java new file mode 100644 index 0000000..e56bab4 --- /dev/null +++ b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/CombinationsTest.java @@ -0,0 +1,194 @@ +/* + * 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.numbers.combinatorics; + +import java.util.Iterator; +import java.util.Comparator; + +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.LexicographicComparator(5, 3)); + checkLexicographicIterator(new Combinations.LexicographicComparator(6, 4)); + checkLexicographicIterator(new Combinations.LexicographicComparator(8, 2)); + checkLexicographicIterator(new Combinations.LexicographicComparator(6, 1)); + checkLexicographicIterator(new Combinations.LexicographicComparator(3, 3)); + checkLexicographicIterator(new Combinations.LexicographicComparator(1, 1)); + checkLexicographicIterator(new Combinations.LexicographicComparator(1, 0)); + checkLexicographicIterator(new Combinations.LexicographicComparator(0, 0)); + checkLexicographicIterator(new Combinations.LexicographicComparator(4, 2)); + checkLexicographicIterator(new Combinations.LexicographicComparator(123, 2)); + } + + @Test(expected=IllegalArgumentException.class) + public void testLexicographicComparatorWrongIterate1() { + final int n = 5; + final int k = 3; + final Comparator<int[]> comp = new Combinations.LexicographicComparator(n, k); + comp.compare(new int[] {1}, new int[] {0, 1, 2}); + } + + @Test(expected=IllegalArgumentException.class) + public void testLexicographicComparatorWrongIterate2() { + final int n = 5; + final int k = 3; + final Comparator<int[]> comp = new Combinations.LexicographicComparator(n, k); + comp.compare(new int[] {0, 1, 2}, new int[] {0, 1, 2, 3}); + } + + @Test(expected=IllegalArgumentException.class) + public void testLexicographicComparatorWrongIterate3() { + final int n = 5; + final int k = 3; + final Comparator<int[]> comp = new Combinations.LexicographicComparator(n, k); + comp.compare(new int[] {1, 2, 5}, new int[] {0, 1, 2}); + } + + @Test(expected=IllegalArgumentException.class) + public void testLexicographicComparatorWrongIterate4() { + final int n = 5; + final int k = 3; + final Comparator<int[]> comp = new Combinations.LexicographicComparator(n, k); + comp.compare(new int[] {1, 2, 4}, new int[] {-1, 1, 2}); + } + + @Test + public void testLexicographicComparatorAccessors() { + final int n = 9; + final int k = 6; + final Combinations.LexicographicComparator comp = + new Combinations.LexicographicComparator(n, k); + Assert.assertEquals(n, comp.getN()); + Assert.assertEquals(k, comp.getK()); + } + + @Test + public void testLexicographicComparator() { + final int n = 5; + final int k = 3; + final Comparator<int[]> comp = new Combinations.LexicographicComparator(n, k); + 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.LexicographicComparator(n, k); + 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 comp Comparator. + */ + private void checkLexicographicIterator(Combinations.LexicographicComparator comp) { + final int n = comp.getN(); + final int k = comp.getK(); + + int[] lastIterate = null; + + long numIterates = 0; + for (int[] iterate : new Combinations(n, k)) { + 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(BinomialCoefficient.value(n, k), numIterates); + } + + @Test(expected=IllegalArgumentException.class) + public void testCombinationsIteratorFail1() { + new Combinations(4, 5).iterator(); + } + @Test(expected=IllegalArgumentException.class) + public void testCombinationsIteratorFail2() { + new Combinations(-1, -2).iterator(); + } +} http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/FactorialDoubleTest.java ---------------------------------------------------------------------- diff --git a/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/FactorialDoubleTest.java b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/FactorialDoubleTest.java new file mode 100644 index 0000000..50c03ba --- /dev/null +++ b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/FactorialDoubleTest.java @@ -0,0 +1,130 @@ +/* + * 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.numbers.combinatorics; + +import org.junit.Assert; +import org.junit.Test; + +/** + * Test cases for the {@link FactorialDouble} class. + */ +public class FactorialDoubleTest { + @Test + public void testFactorialZero() { + Assert.assertEquals("0!", 1, FactorialDouble.create().value(0), 0d); + } + + @Test + public void testFactorialDirect() { + for (int i = 1; i < 21; i++) { + Assert.assertEquals(i + "!", + factorialDirect(i), FactorialDouble.create().value(i), 0d); + } + } + + @Test + public void testLargestFactorialDouble() { + final int n = 170; + Assert.assertTrue(n + "!", + Double.POSITIVE_INFINITY != FactorialDouble.create().value(n)); + } + + @Test + public void testFactorialDoubleTooLarge() { + final int n = 171; + Assert.assertEquals(n + "!", + Double.POSITIVE_INFINITY, FactorialDouble.create().value(n), 0d); + } + + @Test(expected=IllegalArgumentException.class) + public void testNonPositiveArgument() { + FactorialDouble.create().value(-1); + } + + @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 FactorialDouble f = FactorialDouble.create(); + + for (int i = 0; i < max; i++) { + final double expected = factorialDirect(i); + Assert.assertEquals(i + "! ", + expected, f.value(i), 100 * Math.ulp(expected)); + } + } + + @Test + public void testCompareDirectWithCache() { + final int max = 100; + final FactorialDouble f = FactorialDouble.create().withCache(max); + + for (int i = 0; i < max; i++) { + final double expected = factorialDirect(i); + Assert.assertEquals(i + "! ", + expected, f.value(i), 100 * Math.ulp(expected)); + } + } + + @Test + public void testCacheIncrease() { + final int max = 100; + final FactorialDouble f1 = FactorialDouble.create().withCache(max); + final FactorialDouble f2 = f1.withCache(2 * max); + + final int val = max + max / 2; + Assert.assertEquals(f1.value(val), f2.value(val), 0d); + } + + @Test + public void testZeroCache() { + // Ensure that no exception is thrown. + final FactorialDouble f = FactorialDouble.create().withCache(0); + Assert.assertEquals(1, f.value(0), 0d); + Assert.assertEquals(1, f.value(1), 0d); + } + + @Test + public void testUselessCache() { + // Ensure that no exception is thrown. + LogFactorial.create().withCache(1); + LogFactorial.create().withCache(2); + } + + @Test + public void testCacheDecrease() { + final int max = 100; + final FactorialDouble f1 = FactorialDouble.create().withCache(max); + final FactorialDouble f2 = f1.withCache(max / 2); + + final int val = max / 4; + Assert.assertEquals(f1.value(val), f2.value(val), 0d); + } + + /** + * Direct multiplication implementation. + */ + private double factorialDirect(int n) { + double result = 1; + for (int i = 2; i <= n; i++) { + result *= i; + } + return result; + } +} http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/FactorialTest.java ---------------------------------------------------------------------- diff --git a/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/FactorialTest.java b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/FactorialTest.java new file mode 100644 index 0000000..9b5fde4 --- /dev/null +++ b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/FactorialTest.java @@ -0,0 +1,58 @@ +/* + * 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.numbers.combinatorics; + +import org.junit.Assert; +import org.junit.Test; + +/** + * Test cases for the {@link Factorial} class. + */ +public class FactorialTest { + @Test + public void testFactorialZero() { + Assert.assertEquals("0!", 1, Factorial.value(0)); + } + + @Test + public void testFactorial() { + for (int i = 1; i < 21; i++) { + Assert.assertEquals(i + "!", factorial(i), Factorial.value(i)); + } + } + + @Test(expected=IllegalArgumentException.class) + public void testPrecondition1() { + Factorial.value(-1); + } + + @Test(expected=IllegalArgumentException.class) + public void testPrecondition2() { + Factorial.value(21); + } + + /** + * Direct multiplication implementation. + */ + 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-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/LogBinomialCoefficientTest.java ---------------------------------------------------------------------- diff --git a/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/LogBinomialCoefficientTest.java b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/LogBinomialCoefficientTest.java new file mode 100644 index 0000000..24aa734 --- /dev/null +++ b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/LogBinomialCoefficientTest.java @@ -0,0 +1,101 @@ +/* + * 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.numbers.combinatorics; + +import org.junit.Assert; +import org.junit.Test; + +/** + * Test cases for the {@link LogBinomialCoefficient} class. + */ +public class LogBinomialCoefficientTest { + /** Verify that b(0,0) = 1 */ + @Test + public void test0Choose0() { + Assert.assertEquals(LogBinomialCoefficient.value(0, 0), 0d, 0); + } + + @Test + public void testBinomialCoefficient() { + final long[] bcoef5 = { 1, 5, 10, 10, 5, 1 }; + final long[] bcoef6 = { 1, 6, 15, 20, 15, 6, 1 }; + + for (int n = 1; n < 10; n++) { + for (int k = 0; k <= n; k++) { + Assert.assertEquals(n + " choose " + k, + Math.log(BinomialCoefficientTest.binomialCoefficient(n, k)), + LogBinomialCoefficient.value(n, k), 1e-12); + } + } + + final int[] n = { 34, 66, 100, 1500, 1500 }; + final int[] k = { 17, 33, 10, 1500 - 4, 4 }; + for (int i = 0; i < n.length; i++) { + final long expected = BinomialCoefficientTest.binomialCoefficient(n[i], k[i]); + Assert.assertEquals("log(" + n[i] + " choose " + k[i] + ")", + Math.log(expected), + LogBinomialCoefficient.value(n[i], k[i]), + 0d); + } + } + + @Test(expected=CombinatoricsException.class) + public void testBinomialCoefficientFail1() { + LogBinomialCoefficient.value(4, 5); + } + + @Test(expected=CombinatoricsException.class) + public void testBinomialCoefficientFail2() { + LogBinomialCoefficient.value(-1, -2); + } + + /** + * 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 exactResult = -1; + boolean shouldThrow = false; + boolean didThrow = false; + try { + BinomialCoefficient.value(n, k); + } catch (ArithmeticException ex) { + didThrow = true; + } + try { + exactResult = BinomialCoefficientTest.binomialCoefficient(n, k); + } catch (ArithmeticException ex) { + shouldThrow = true; + } + + if (!shouldThrow && exactResult > 1) { + Assert.assertEquals(n + " choose " + k, 1, + LogBinomialCoefficient.value(n, k) / Math.log(exactResult), 1e-10); + } + } + } + + final int n = 10000; + final double actualOverExpected = LogBinomialCoefficient.value(n, 3) / + Math.log(BinomialCoefficientTest.binomialCoefficient(n, 3)); + Assert.assertEquals(1, actualOverExpected, 1e-10); + } +} http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/LogFactorialTest.java ---------------------------------------------------------------------- diff --git a/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/LogFactorialTest.java b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/LogFactorialTest.java new file mode 100644 index 0000000..bb223ba --- /dev/null +++ b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/LogFactorialTest.java @@ -0,0 +1,118 @@ +/* + * 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.numbers.combinatorics; + +import org.apache.commons.numbers.gamma.LogGamma; + +import org.junit.Assert; +import org.junit.Test; + +/** + * Test cases for the {@link LogFactorial} class. + */ +public class LogFactorialTest { + @Test(expected=IllegalArgumentException.class) + public void testNonPositiveArgument() { + LogFactorial.create().withCache(-1); + } + + @Test + public void testDelegation() { + final LogFactorial f = LogFactorial.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 leads to difference + // wrt the "direct" computation. + + final int max = 100; + final LogFactorial f = LogFactorial.create(); + + for (int i = 0; i < max; i++) { + final double expected = logFactorial(i); + Assert.assertEquals(i + "! ", + expected, f.value(i), 2 * Math.ulp(expected)); + } + } + + @Test + public void testCompareDirectWithCache() { + final int max = 1000; + final LogFactorial f = LogFactorial.create().withCache(max); + + for (int i = 0; i < max; i++) { + final double expected = logFactorial(i); + Assert.assertEquals(i + "! ", + expected, f.value(i), 0d); + } + } + + @Test + public void testZeroCache() { + // Ensure that no exception is thrown. + final LogFactorial f = LogFactorial.create().withCache(0); + Assert.assertEquals(0, f.value(0), 0d); + Assert.assertEquals(0, f.value(1), 0d); + } + + @Test + public void testUselessCache() { + // Ensure that no exception is thrown. + LogFactorial.create().withCache(1); + LogFactorial.create().withCache(2); + } + + @Test + public void testCacheIncrease() { + final int max = 100; + final LogFactorial f1 = LogFactorial.create().withCache(max); + final LogFactorial f2 = f1.withCache(2 * max); + + final int val = max + max / 2; + final double expected = logFactorial(val); + Assert.assertEquals(expected, f2.value(val), 0d); + } + + @Test + public void testCacheDecrease() { + final int max = 100; + final LogFactorial f1 = LogFactorial.create().withCache(max); + final LogFactorial f2 = f1.withCache(max / 2); + + final int val = max / 4; + final double expected = logFactorial(val); + Assert.assertEquals(expected, f2.value(val), 0d); + } + + // Direct implementation. + private double logFactorial(final int n) { + double logSum = 0; + for (int i = 2; i <= n; i++) { + logSum += Math.log(i); + } + return logSum; + } +}
