Author: erans
Date: Fri Sep 6 15:32:37 2013
New Revision: 1520605
URL: http://svn.apache.org/r1520605
Log:
MATH-1027
Added accessors and (lexicographic) comparator.
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/Combinations.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinationsTest.java
Modified:
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=1520605&r1=1520604&r2=1520605&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/Combinations.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/Combinations.java
Fri Sep 6 15:32:37 2013
@@ -17,8 +17,13 @@
package org.apache.commons.math3.util;
import java.util.Iterator;
+import java.util.Comparator;
+import java.util.Arrays;
import java.util.NoSuchElementException;
+import java.io.Serializable;
import org.apache.commons.math3.exception.MathInternalError;
+import org.apache.commons.math3.exception.DimensionMismatchException;
+import org.apache.commons.math3.exception.OutOfRangeException;
/**
* Utility to create <a href="http://en.wikipedia.org/wiki/Combination";>
@@ -96,6 +101,24 @@ public class Combinations implements Ite
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() {
@@ -120,6 +143,24 @@ public class Combinations implements Ite
}
/**
+ * 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>
@@ -278,4 +319,89 @@ public class Combinations implements Ite
throw new UnsupportedOperationException();
}
}
+
+ /**
+ * Defines the lexicographic ordering of combinations, using
+ * the {@link #lexNorm(int[],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.
+ */
+ public 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}).
+ */
+ 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, (long) i);
+ }
+ return ret;
+ }
+ }
}
Modified:
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=1520605&r1=1520604&r2=1520605&view=diff
==============================================================================
---
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinationsTest.java
(original)
+++
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinationsTest.java
Fri Sep 6 15:32:37 2013
@@ -17,6 +17,9 @@
package org.apache.commons.math3.util;
import java.util.Iterator;
+import java.util.Comparator;
+import org.apache.commons.math3.exception.DimensionMismatchException;
+import org.apache.commons.math3.exception.OutOfRangeException;
import org.apache.commons.math3.exception.MathIllegalArgumentException;
import org.junit.Assert;
import org.junit.Test;
@@ -26,19 +29,93 @@ import org.junit.Test;
*
* @version $Id$
*/
-public class CombinationsTest {
+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), 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);
+ 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
@@ -71,25 +148,35 @@ public class CombinationsTest {
* 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;
+ 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);
- final long curLex = lexNorm(iterate, n);
- Assert.assertTrue(curLex > lastLex);
- lastLex = curLex;
- 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;
}
- Assert.assertEquals(CombinatoricsUtils.binomialCoefficient(n, k),
length);
+
+ // Check the number of iterates.
+ Assert.assertEquals(CombinatoricsUtils.binomialCoefficient(n, k),
+ numIterates);
}
@Test
@@ -108,20 +195,4 @@ public class CombinationsTest {
// 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;
- }
}
