commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From er...@apache.org
Subject svn commit: r1519924 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math3/util/ test/java/org/apache/commons/math3/util/
Date Wed, 04 Sep 2013 07:28:48 GMT
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;
-    }
 }



Mime
View raw message