Author: erans
Date: Wed Sep 4 07:28:48 2013
New Revision: 1519924
URL: http://svn.apache.org/r1519924
Log:
MATH-1027
Transferred code from "CombinatoricsUtils" to new class "Combinations".
Made "checkBinomial" public in "CombinatoricsUtils".
Added:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/Combinations.java
(with props)
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinationsTest.java
(with props)
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/CombinatoricsUtils.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinatoricsUtilsTest.java
Added:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/Combinations.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/Combinations.java?rev=1519924&view=auto
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/Combinations.java
(added)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/Combinations.java
Wed Sep 4 07:28:48 2013
@@ -0,0 +1,281 @@
+/*
+ * 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.math3.util;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import org.apache.commons.math3.exception.MathInternalError;
+
+/**
+ * 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.
+ *
+ * @version $Id$
+ * @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}.
+ */
+ public static enum IterationOrder {
+ /** Lexicographic order. */
+ LEXICOGRAPHIC
+ }
+
+ /**
+ * Creates an instance whose range is the k-element subsets of
+ * {0, ..., n - 1} represented as {@code int[]} arrays.
+ * The {@link #iterator() iteration order} is
+ * {@link IterationOrder lexicographic}.
+ *
+ * @see #Combinations(int,int,IterationOrder)
+ *
+ * @param n Size of the set from which subsets are selected.
+ * @param k Size of the subsets to be enumerated.
+ * @throws org.apache.commons.math3.exception.NotPositiveException if
{@code n < 0}.
+ * @throws org.apache.commons.math3.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.math3.exception.NotPositiveException if
{@code n < 0}.
+ * @throws org.apache.commons.math3.exception.NumberIsTooLargeException if
{@code k > n}.
+ */
+ public Combinations(int n,
+ int k,
+ IterationOrder iterationOrder) {
+ CombinatoricsUtils.checkBinomial(n, k);
+ this.n = n;
+ this.k = k;
+ this.iterationOrder = iterationOrder;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Iterator<int[]> iterator() {
+ if (k == 0) {
+ return new SingletonIterator(new int[]{});
+ }
+ if (k == n) {
+ // TODO: once getNatural is extracted from RandomDataGenerator,
use it
+ final int[] natural = new int[n];
+ for (int i = 0; i < n; i++) {
+ natural[i] = i;
+ }
+ return new SingletonIterator(natural);
+ }
+
+ switch (iterationOrder) {
+ case LEXICOGRAPHIC:
+ return new LexicographicIterator(n, k);
+ default:
+ throw new MathInternalError(); // Should never happen.
+ }
+ }
+
+ /**
+ * 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
+ */
+ public 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}
+ */
+ public boolean hasNext() {
+ return more;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ 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);
+ //final int[] ret = MathArrays.copyOf(c, k + 1);
+
+ // 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] = c[1] + 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.
+ */
+ 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
+ */
+ public SingletonIterator(final int[] singleton) {
+ this.singleton = singleton;
+ }
+ /** @return True until next is called the first time, then false */
+ public boolean hasNext() {
+ return more;
+ }
+ /** @return the singleton in first activation; throws NSEE thereafter
*/
+ public int[] next() {
+ if (more) {
+ more = false;
+ return singleton;
+ } else {
+ throw new NoSuchElementException();
+ }
+ }
+ /** Not supported */
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ }
+}
Propchange:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/Combinations.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/Combinations.java
------------------------------------------------------------------------------
svn:keywords = Id Revision
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/CombinatoricsUtils.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/CombinatoricsUtils.java?rev=1519924&r1=1519923&r2=1519924&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/CombinatoricsUtils.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/CombinatoricsUtils.java
Wed Sep 4 07:28:48 2013
@@ -17,7 +17,6 @@
package org.apache.commons.math3.util;
import java.util.Iterator;
-import java.util.NoSuchElementException;
import java.util.concurrent.atomic.AtomicReference;
import org.apache.commons.math3.exception.MathArithmeticException;
@@ -420,7 +419,7 @@ public final class CombinatoricsUtils {
}
/**
- * Returns an Iterator whose range is the k-element subsets of {0, ..., n
- 1}
+ * 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
@@ -433,187 +432,14 @@ public final class CombinatoricsUtils {
* 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.
*
- * @param n size of the set from which subsets are selected
- * @param k size of the subsets to be enumerated
- * @return an Iterator over the k-sets in n
+ * @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) {
- checkBinomial(n, k);
- if (k == 0) {
- return new SingletonIterator(new int[]{});
- }
- if (k == n) {
- // TODO: once getNatural is extracted from RandomDataGenerator,
use it
- final int[] natural = new int[n];
- for (int i = 0; i < n; i++) {
- natural[i] = i;
- }
- return new SingletonIterator(natural);
- }
- return new LexicographicCombinationIterator(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 LexicographicCombinationIterator 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
- */
- public LexicographicCombinationIterator(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}
- */
- public boolean hasNext() {
- return more;
- }
-
- /**
- * {@inheritDoc}
- */
- 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);
- //final int[] ret = MathArrays.copyOf(c, k + 1);
-
- // 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] = c[1] + 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.
- */
- 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
- */
- public SingletonIterator(final int[] singleton) {
- this.singleton = singleton;
- }
- /** @return True until next is called the first time, then false */
- public boolean hasNext() {
- return more;
- }
- /** @return the singleton in first activation; throws NSEE thereafter
*/
- public int[] next() {
- if (more) {
- more = false;
- return singleton;
- } else {
- throw new NoSuchElementException();
- }
- }
- /** Not supported */
- public void remove() {
- throw new UnsupportedOperationException();
- }
+ return new Combinations(n, k,
Combinations.IterationOrder.LEXICOGRAPHIC).iterator();
}
/**
@@ -624,7 +450,10 @@ public final class CombinatoricsUtils {
* @throws NotPositiveException if {@code n < 0}.
* @throws NumberIsTooLargeException if {@code k > n}.
*/
- private static void checkBinomial(final int n, final int k) throws
NumberIsTooLargeException, NotPositiveException {
+ 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);
@@ -633,5 +462,4 @@ public final class CombinatoricsUtils {
throw new
NotPositiveException(LocalizedFormats.BINOMIAL_NEGATIVE_PARAMETER, n);
}
}
-
}
Added:
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinationsTest.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinationsTest.java?rev=1519924&view=auto
==============================================================================
---
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinationsTest.java
(added)
+++
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinationsTest.java
Wed Sep 4 07:28:48 2013
@@ -0,0 +1,127 @@
+/*
+ * 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.math3.util;
+
+import java.util.Iterator;
+import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * Tests for the {@link Combinations} class.
+ *
+ * @version $Id$
+ */
+public class CombinationsTest {
+ @Test
+ public void testLexicographicIterator() {
+ checkLexicographicIterator(new Combinations(5, 3), 5, 3);
+ checkLexicographicIterator(new Combinations(6, 4), 6, 4);
+ checkLexicographicIterator(new Combinations(8, 2), 8, 2);
+ checkLexicographicIterator(new Combinations(6, 1), 6, 1);
+ checkLexicographicIterator(new Combinations(3, 3), 3, 3);
+ checkLexicographicIterator(new Combinations(1, 1), 1, 1);
+ checkLexicographicIterator(new Combinations(1, 0), 1, 0);
+ checkLexicographicIterator(new Combinations(0, 0), 0, 0);
+ checkLexicographicIterator(new Combinations(4, 2), 4, 2);
+ checkLexicographicIterator(new Combinations(123, 2), 123, 2);
+ }
+
+ @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.
+ * @param n Size of universe.
+ * @param k Size of subsets.
+ */
+ private void checkLexicographicIterator(Iterable<int[]> c,
+ int n,
+ int k) {
+ long lastLex = -1;
+ long length = 0;
+ for (int[] iterate : c) {
+ Assert.assertEquals(k, iterate.length);
+ final long curLex = lexNorm(iterate, n);
+ Assert.assertTrue(curLex > lastLex);
+ lastLex = curLex;
+ length++;
+ for (int i = 1; i < iterate.length; i++) {
+ Assert.assertTrue(iterate[i] > iterate[i - 1]);
+ }
+ }
+ Assert.assertEquals(CombinatoricsUtils.binomialCoefficient(n, k),
length);
+ }
+
+ @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
+ }
+ }
+
+ /**
+ * Returns the value represented by the digits in the input array in
reverse order.
+ * For example [3,2,1] returns 123.
+ *
+ * @param iterate input array
+ * @param n size of universe
+ * @return lexicographic norm
+ */
+ private long lexNorm(int[] iterate, int n) {
+ long ret = 0;
+ for (int i = iterate.length - 1; i >= 0; i--) {
+ ret += iterate[i] * ArithmeticUtils.pow(n, (long) i);
+ }
+ return ret;
+ }
+}
Propchange:
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinationsTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange:
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinationsTest.java
------------------------------------------------------------------------------
svn:keywords = Id Revision
Modified:
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinatoricsUtilsTest.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinatoricsUtilsTest.java?rev=1519924&r1=1519923&r2=1519924&view=diff
==============================================================================
---
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinatoricsUtilsTest.java
(original)
+++
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinatoricsUtilsTest.java
Wed Sep 4 07:28:48 2013
@@ -32,7 +32,7 @@ import org.junit.Test;
/**
* Test cases for the {@link CombinatoricsUtils} class.
*
- * @version $Id: $
+ * @version $Id$
*/
public class CombinatoricsUtilsTest {
@@ -311,6 +311,24 @@ public class CombinatoricsUtilsTest {
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
*/
@@ -357,89 +375,4 @@ public class CombinatoricsUtilsTest {
}
return result;
}
-
- @Test
- public void testCombinationsIterator() {
- Iterator<int[]> combinationsIterator =
CombinatoricsUtils.combinationsIterator(5, 3);
- checkIterator(combinationsIterator, 5, 3);
- combinationsIterator = CombinatoricsUtils.combinationsIterator(6, 4);
- checkIterator(combinationsIterator, 6, 4);
- combinationsIterator = CombinatoricsUtils.combinationsIterator(8, 2);
- checkIterator(combinationsIterator, 8, 2);
- combinationsIterator = CombinatoricsUtils.combinationsIterator(6, 1);
- checkIterator(combinationsIterator, 6, 1);
- combinationsIterator = CombinatoricsUtils.combinationsIterator(3, 3);
- checkIterator(combinationsIterator, 3, 3);
- combinationsIterator = CombinatoricsUtils.combinationsIterator(1, 1);
- checkIterator(combinationsIterator, 1, 1);
- combinationsIterator = CombinatoricsUtils.combinationsIterator(1, 1);
- checkIterator(combinationsIterator, 1, 1);
- combinationsIterator = CombinatoricsUtils.combinationsIterator(1, 0);
- checkIterator(combinationsIterator, 1, 0);
- combinationsIterator = CombinatoricsUtils.combinationsIterator(0, 0);
- checkIterator(combinationsIterator, 0, 0);
- combinationsIterator = CombinatoricsUtils.combinationsIterator(4, 2);
- checkIterator(combinationsIterator, 4, 2);
- combinationsIterator = CombinatoricsUtils.combinationsIterator(123, 2);
- checkIterator(combinationsIterator, 123, 2);
- }
-
- /**
- * Verifies that the iterator generates a lexicographically
- * increasing sequence of b(n,k) arrays, each having length k
- * and each array itself increasing.
- *
- * @param iterator
- * @param n size of universe
- * @param k size of subsets
- */
- private void checkIterator(Iterator<int[]> iterator, int n, int k) {
- long lastLex = -1;
- long length = 0;
- while (iterator.hasNext()) {
- final int[] iterate = iterator.next();
- Assert.assertEquals(k, iterate.length);
- final long curLex = lexNorm(iterate, n);
- Assert.assertTrue(curLex > lastLex);
- lastLex = curLex;
- length++;
- for (int i = 1; i < iterate.length; i++) {
- Assert.assertTrue(iterate[i] > iterate[i - 1]);
- }
- }
- Assert.assertEquals(CombinatoricsUtils.binomialCoefficient(n, k),
length);
- }
-
- @Test
- public void testCombinationsIteratorFail() {
- try {
- CombinatoricsUtils.combinationsIterator(4, 5);
- Assert.fail("expecting MathIllegalArgumentException");
- } catch (MathIllegalArgumentException ex) {
- // ignored
- }
-
- try {
- CombinatoricsUtils.combinationsIterator(-1, -2);
- Assert.fail("expecting MathIllegalArgumentException");
- } catch (MathIllegalArgumentException ex) {
- // ignored
- }
- }
-
- /**
- * Returns the value represented by the digits in the input array in
reverse order.
- * For example [3,2,1] returns 123.
- *
- * @param iterate input array
- * @param n size of universe
- * @return lexicographic norm
- */
- private long lexNorm(int[] iterate, int n) {
- long ret = 0;
- for (int i = iterate.length - 1; i >= 0; i--) {
- ret += iterate[i] * ArithmeticUtils.pow(n, (long) i);
- }
- return ret;
- }
}
