You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ps...@apache.org on 2013/08/24 23:55:36 UTC
svn commit: r1517203 [2/2] - in /commons/proper/math/trunk/src: changes/
main/java/org/apache/commons/math3/analysis/differentiation/
main/java/org/apache/commons/math3/analysis/interpolation/
main/java/org/apache/commons/math3/analysis/polynomials/ ma...
Added: 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=1517203&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinatoricsUtilsTest.java (added)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinatoricsUtilsTest.java Sat Aug 24 21:55:35 2013
@@ -0,0 +1,443 @@
+/*
+ * 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.ArrayList;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.commons.math3.exception.MathArithmeticException;
+import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.apache.commons.math3.exception.NotPositiveException;
+import org.apache.commons.math3.exception.NumberIsTooLargeException;
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * Test cases for the {@link CombinatoricsUtils} class.
+ *
+ * @version $Id: $
+ */
+public class CombinatoricsUtilsTest {
+
+ /** cached binomial coefficients */
+ private static final List<Map<Integer, Long>> binomialCache = new ArrayList<Map<Integer, Long>>();
+
+ /** 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 MathArithmeticException");
+ } catch (MathArithmeticException ex) {
+ // ignored
+ }
+ try {
+ CombinatoricsUtils.binomialCoefficient(67, 34);
+ Assert.fail("expecting MathArithmeticException");
+ } catch (MathArithmeticException 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 (MathArithmeticException ex) {
+ didThrow = true;
+ }
+ try {
+ exactResult = binomialCoefficient(n, k);
+ } catch (MathArithmeticException 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 MathArithmeticException");
+ } catch (MathArithmeticException 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() {
+
+ Assert.assertEquals(1, CombinatoricsUtils.stirlingS2(0, 0));
+
+ for (int n = 1; n < 30; ++n) {
+ Assert.assertEquals(0, CombinatoricsUtils.stirlingS2(n, 0));
+ 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),
+ CombinatoricsUtils.stirlingS2(n, n - 1));
+ }
+ Assert.assertEquals(1, CombinatoricsUtils.stirlingS2(n, n));
+ }
+ Assert.assertEquals(536870911l, CombinatoricsUtils.stirlingS2(30, 2));
+ Assert.assertEquals(576460752303423487l, CombinatoricsUtils.stirlingS2(60, 2));
+
+ Assert.assertEquals( 25, CombinatoricsUtils.stirlingS2( 5, 3));
+ Assert.assertEquals( 90, CombinatoricsUtils.stirlingS2( 6, 3));
+ Assert.assertEquals( 65, CombinatoricsUtils.stirlingS2( 6, 4));
+ Assert.assertEquals( 301, CombinatoricsUtils.stirlingS2( 7, 3));
+ Assert.assertEquals( 350, CombinatoricsUtils.stirlingS2( 7, 4));
+ Assert.assertEquals( 140, CombinatoricsUtils.stirlingS2( 7, 5));
+ Assert.assertEquals( 966, CombinatoricsUtils.stirlingS2( 8, 3));
+ Assert.assertEquals( 1701, CombinatoricsUtils.stirlingS2( 8, 4));
+ Assert.assertEquals( 1050, CombinatoricsUtils.stirlingS2( 8, 5));
+ Assert.assertEquals( 266, CombinatoricsUtils.stirlingS2( 8, 6));
+ Assert.assertEquals( 3025, CombinatoricsUtils.stirlingS2( 9, 3));
+ Assert.assertEquals( 7770, CombinatoricsUtils.stirlingS2( 9, 4));
+ Assert.assertEquals( 6951, CombinatoricsUtils.stirlingS2( 9, 5));
+ Assert.assertEquals( 2646, CombinatoricsUtils.stirlingS2( 9, 6));
+ Assert.assertEquals( 462, CombinatoricsUtils.stirlingS2( 9, 7));
+ Assert.assertEquals( 9330, CombinatoricsUtils.stirlingS2(10, 3));
+ Assert.assertEquals(34105, CombinatoricsUtils.stirlingS2(10, 4));
+ Assert.assertEquals(42525, CombinatoricsUtils.stirlingS2(10, 5));
+ Assert.assertEquals(22827, CombinatoricsUtils.stirlingS2(10, 6));
+ Assert.assertEquals( 5880, CombinatoricsUtils.stirlingS2(10, 7));
+ Assert.assertEquals( 750, CombinatoricsUtils.stirlingS2(10, 8));
+
+ }
+
+ @Test(expected=NotPositiveException.class)
+ public void testStirlingS2NegativeN() {
+ CombinatoricsUtils.stirlingS2(3, -1);
+ }
+
+ @Test(expected=NumberIsTooLargeException.class)
+ public void testStirlingS2LargeK() {
+ CombinatoricsUtils.stirlingS2(3, 4);
+ }
+
+ @Test(expected=MathArithmeticException.class)
+ public void testStirlingS2Overflow() {
+ CombinatoricsUtils.stirlingS2(26, 9);
+ }
+
+ /**
+ * Exact (caching) recursive implementation to test against
+ */
+ private long binomialCoefficient(int n, int k) throws MathArithmeticException {
+ 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 MathArithmeticException();
+ }
+ 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;
+ }
+
+ @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);
+ }
+
+ /**
+ * Verifies that the iterator generates a lexicographically
+ * increasing sequence of b(n,k) arrays, each having length k
+ * and each array itself increasing.
+ *
+ * Note: the lexicographic order check only works for n < 10.
+ *
+ * @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);
+ 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
+ * @return lexicographic norm
+ */
+ private long lexNorm(int[] iterate) {
+ long ret = 0;
+ for (int i = iterate.length - 1; i >= 0; i--) {
+ ret += iterate[i] * ArithmeticUtils.pow(10l, (long) i);
+ }
+ return ret;
+ }
+}
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java Sat Aug 24 21:55:35 2013
@@ -14,6 +14,7 @@
package org.apache.commons.math3.util;
import java.util.Arrays;
+import java.util.Iterator;
import org.apache.commons.math3.TestUtils;
import org.apache.commons.math3.exception.DimensionMismatchException;
Re: svn commit: r1517203 [2/2] - in /commons/proper/math/trunk/src:
changes/ main/java/org/apache/commons/math3/analysis/differentiation/
main/java/org/apache/commons/math3/analysis/interpolation/
main/java/org/apache/commons/math3/analysis/polynomials/ ma...
Posted by Gilles <gi...@harfang.homelinux.org>.
On Sun, 25 Aug 2013 09:03:56 -0700, Phil Steitz wrote:
> On 8/25/13 7:47 AM, Gilles wrote:
>> Hi.
>>
>>> [...]
>>> +
>>> + /**
>>> + * Verifies that the iterator generates a lexicographically
>>> + * increasing sequence of b(n,k) arrays, each having length k
>>> + * and each array itself increasing.
>>> + *
>>> + * Note: the lexicographic order check only works for n < 10.
>>
>> What about not using a fixed base (cf. below)?
>
> Thanks for the review!
>
> Yes, I think below would work. The key is the base, as you note.
> Or being less lazy and just actually directly implementing
> lexicographic order check. I did not see the need to test with n >
> 10; but I would be fine with the change below to allow it.
Committed in revision 1517338.
Gilles
>
> Phil
>>
>>> + *
>>> + * @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);
>> ^^^^^^^^^^^^^^^
>> Replace with
>> 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]);
>>> + }
>>> + }
>>
>>> [...]
>>
>>> +
>>> + /**
>>> + * 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
>>> + * @return lexicographic norm
>>> + */
>>> + private long lexNorm(int[] iterate) {
>> ^^^
>> Replace with
>> private long lexNorm(int[] iterate, int n)
>>
>>> + long ret = 0;
>>> + for (int i = iterate.length - 1; i >= 0; i--) {
>>> + ret += iterate[i] * ArithmeticUtils.pow(10l, (long)
>>> i);
>> ^^^^^^^^^^^^^^
>> Replace with
>> ret += iterate[i] * ArithmeticUtils.pow(n, (long) i);
>>
>>> + }
>>> + return ret;
>>> + }
>>> +}
>>
>>> [...]
>>
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: svn commit: r1517203 [2/2] - in /commons/proper/math/trunk/src:
changes/ main/java/org/apache/commons/math3/analysis/differentiation/ main/java/org/apache/commons/math3/analysis/interpolation/
main/java/org/apache/commons/math3/analysis/polynomials/ ma...
Posted by Phil Steitz <ph...@gmail.com>.
On 8/25/13 7:47 AM, Gilles wrote:
> Hi.
>
>> [...]
>> +
>> + /**
>> + * Verifies that the iterator generates a lexicographically
>> + * increasing sequence of b(n,k) arrays, each having length k
>> + * and each array itself increasing.
>> + *
>> + * Note: the lexicographic order check only works for n < 10.
>
> What about not using a fixed base (cf. below)?
Thanks for the review!
Yes, I think below would work. The key is the base, as you note.
Or being less lazy and just actually directly implementing
lexicographic order check. I did not see the need to test with n >
10; but I would be fine with the change below to allow it.
Phil
>
>> + *
>> + * @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);
> ^^^^^^^^^^^^^^^
> Replace with
> 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]);
>> + }
>> + }
>
>> [...]
>
>> +
>> + /**
>> + * 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
>> + * @return lexicographic norm
>> + */
>> + private long lexNorm(int[] iterate) {
> ^^^
> Replace with
> private long lexNorm(int[] iterate, int n)
>
>> + long ret = 0;
>> + for (int i = iterate.length - 1; i >= 0; i--) {
>> + ret += iterate[i] * ArithmeticUtils.pow(10l, (long) i);
> ^^^^^^^^^^^^^^
> Replace with
> ret += iterate[i] * ArithmeticUtils.pow(n, (long) i);
>
>> + }
>> + return ret;
>> + }
>> +}
>
>> [...]
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: svn commit: r1517203 [2/2] - in /commons/proper/math/trunk/src:
changes/ main/java/org/apache/commons/math3/analysis/differentiation/
main/java/org/apache/commons/math3/analysis/interpolation/
main/java/org/apache/commons/math3/analysis/polynomials/ ma...
Posted by Gilles <gi...@harfang.homelinux.org>.
Hi.
> [...]
> +
> + /**
> + * Verifies that the iterator generates a lexicographically
> + * increasing sequence of b(n,k) arrays, each having length k
> + * and each array itself increasing.
> + *
> + * Note: the lexicographic order check only works for n < 10.
What about not using a fixed base (cf. below)?
> + *
> + * @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);
^^^^^^^^^^^^^^^
Replace with
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]);
> + }
> + }
> [...]
> +
> + /**
> + * 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
> + * @return lexicographic norm
> + */
> + private long lexNorm(int[] iterate) {
^^^
Replace with
private long lexNorm(int[] iterate, int n)
> + long ret = 0;
> + for (int i = iterate.length - 1; i >= 0; i--) {
> + ret += iterate[i] * ArithmeticUtils.pow(10l, (long) i);
^^^^^^^^^^^^^^
Replace with
ret += iterate[i] * ArithmeticUtils.pow(n, (long) i);
> + }
> + return ret;
> + }
> +}
> [...]
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Improving combinationIterator?
Posted by James Carman <ja...@carmanconsulting.com>.
I can imagine it in CollectionUtils if it's generified.
On Tue, Aug 27, 2013 at 2:12 AM, Phil Steitz <ph...@gmail.com> wrote:
> On 8/26/13 4:37 AM, Gilles wrote:
>> On Sun, 25 Aug 2013 17:14:37 -0700, Phil Steitz wrote:
>>> On 8/25/13 9:59 AM, Gilles wrote:
>>>> On Sun, 25 Aug 2013 09:19:41 -0700, Phil Steitz wrote:
>>>>> On 8/25/13 8:10 AM, Gilles wrote:
>>>>>> On Sat, 24 Aug 2013 21:55:36 -0000, psteitz@apache.org wrote:
>>>>>>
>>>>>>> [...]
>>>>>>
>>>>>> I wonder whether the utility should involve the creation of
>>>>>> an instance of a bona fide "Combination" class.
>>>>>> I.e. instead of a "naked"
>>>>>> Iterator<int[]> combinationIterator(int n, int k)
>>>>>> there would be
>>>>>> Iterator<Combination> combinationIterator(int n, int k)
>>>>>> where "Combination" would provide an accessor
>>>>>> public int[] toArray() {
>>>>>> // ...
>>>>>> }
>>>>>
>>>>> I need the "naked arrays" generated very quickly with minimal
>>>>> overhead for the K-S use case.
>>>>
>>>> The only "overhead" would be the creation of an instance for
>>>> wrapping the "int[]".
>>>> [As allocation is fairly cheap in Java, that should not be a
>>>> problem.]
>>>>
>>>>> My use case uses the arrays
>>>>> directly, but others could use the indices to extract objects from
>>>>> lists. For example, what I thought would be natural would be to
>>>>> add
>>>>> public static <T> Iterator<List<T>> combinationsIterator(List<T>
>>>>> list, int k)
>>>>
>>>> Would this be the base implementation, from which your case would
>>>> be implemented by retrieving "Integer" from the list and
>>>> copy/convert
>>>> them into an "int[]"?
>>>
>>> No, the opposite actually. The base impl is what exists now. It
>>> works efficiently directly on an int[] array to compute the indices
>>> within the source list (in my use case, {0, 1, ..., n-1} which is
>>> actually canonical). Then if you want to source subsets of objects
>>> from a list of objects, you can compute the int[] array that
>>> actually *is* the combination and extract the corresponding elements
>>> from the list.
>>
>> I got it.
>>
>>>>
>>>>>
>>>>> What you would get out of this is element lists. And the
>>>>> implementation could postpone copy / creation until the indices
>>>>> have
>>>>> been selected using the existing method.
>>>>
>>>> I don't follow ...
>>>
>>> See above. I am probably still not explaining clearly what I have
>>> in mind. To me, a "combination" is a subset of the integers {0,
>>> ..., n-1}. Technically it is a set, not a list, but there is a
>>> natural order available and enumeration can work easier if you use
>>> that order and adopt the convention that you represent combinations
>>> as ordered lists of integers. The LexicographicCombinationIterator
>>> that I committed does that, using primitive arrays to represent the
>>> lists. The iterator itself uses a primitive array of int[] to
>>> maintain state and create successive iterates. Use of a single
>>> primitive array eliminates all object creation / garbage collection,
>>> which is not necessary to just enumerate the combinations. Once you
>>> have a "true" combination represented as an array of int[], you can
>>> use it to specify a "combination" (really sample or subset) of a
>>> list of any kind of object.
>>
>> So, IIUC it would be useful to have a utility like
>> -----
>> public static List<T> getSample(List<T> elements,
>> int[] combination) {
>> final List<T> samples = new ArrayList<T>(combination.length);
>> for (int index : combination) {
>> samples.add(elements.get(index));
>> }
>> }
>
> Yes, that is what the List version would use. Not sure how
> generically useful it would be, but I can imagine other use cases.
> It might be best to call it filter or subList or something and put
> it in MathArrays. Not sure where it would belong as a generic utility.
>
>
>> -----
>>
>>>>
>>>>> I am not yet sold on the
>>>>> value of "Combination" as an abstraction, since what you really
>>>>> use
>>>>> is just the list of selected elements.
>>>>
>>>> Maybe "Combination" is not worth implementing indeed; but what
>>>> about
>>>> a "Combinations" class:
>>>>
>>>> public class Combinations implements Iterable<int[]> {
>>>> private final int n;
>>>> private final int k;
>>>>
>>>> public Combinations(int n, int k) {
>>>> // ...
>>>> }
>>>>
>>>> public Iterator<int[]> iterator() {
>>>> return new LexicographicCombinationIterator(n, k);
>>>> }
>>>>
>>>> public Comparator<int[]> comparator() {
>>>> return new LexicographicCombinationComparator(n, k);
>>>> }
>>>>
>>>> private static class LexicographicCombinationIterator implements
>>>> Iterator<int[]> {
>>>> // [Your implementation]
>>>> }
>>>>
>>>> private static class LexicographicCombinationComparator
>>>> implements Comparator<int[]> {
>>>> public int compare(int[], int[]) {
>>>> // ... using e.g. "lexNorm" implementation.
>>>> }
>>>> }
>>>> }
>>>>
>>>> Being "Iterable" allows nice usage in a "for" loop:
>>>>
>>>> for (int[] combination : new Combinations(4, 2)) {
>>>> // ... etc.
>>>> }
>>>
>>> I thought about that and that is what I meant by the original
>>> suggestion that we possibly make the
>>> LexicographicCombinationsIterator a public class. I just don't see
>>> the practical use cases for it as a standalone class.
>>
>> The "for"-loop example above uses the iterator functionality but
>> in a much less verbose way (no explicit calls to "hasNext()" and
>> "next()").
>> This is standard practice for everything that can be handled as a
>> collection.
>>
>> Then, we can also have your iterator factory method:
>> -----
>> public static Iterator<int[]> combinationsIterator(int n, int k) {
>> return new Combinations(4, 2).iterator();
>> }
>> -----
>>
>> Then, we also don't hide some code in "test" where it could be made
>> visible and be used elsewhere (cf. "lexNorm").
>
> OK, I see your point.
>>
>>> What I have
>>> immediate practical need for is just a way to get an Iterator<int[]>
>>> based on <n,k>. As you note above, it is the Iterator that is
>>> useful. I can imagine use cases for the object-list version
>>> public static <T> Iterator<List<T>> combinationsIterator(List<T>
>>> list, int k ) though. If we do extract a public class, I would
>>> prefer that it be called something like CombinationsIterator.
>>
>> I think that a design based on the "Iterable" interface is
>> preferrable.
>> From it you can always get the iterator functionality (by
>> definition of
>> the interface), while the reverse is not true.
>
> Agreed.
>>
>>> If we
>>> have other iteration strategies that we want to implement, we could
>>> make it an abstract parent for LexicographicCombinationsIterator. I
>>> would recommend holding off complicating the design / structure
>>> though until we have these though.
>>
>> Sorry to insist but it is not a complication, it is a
>> _simplification_ ;-)
>> Instead of a specifically named method ("combinationsIterator"),
>> we rely
>> on the standard API ("Iterable") of the Java language.
>
> Yeah, I get it now. Go for it or open a ticket so we don't forget.
>
> Phil
>>
>>
>> Gilles
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Improving combinationIterator?
Posted by Phil Steitz <ph...@gmail.com>.
On 8/26/13 4:37 AM, Gilles wrote:
> On Sun, 25 Aug 2013 17:14:37 -0700, Phil Steitz wrote:
>> On 8/25/13 9:59 AM, Gilles wrote:
>>> On Sun, 25 Aug 2013 09:19:41 -0700, Phil Steitz wrote:
>>>> On 8/25/13 8:10 AM, Gilles wrote:
>>>>> On Sat, 24 Aug 2013 21:55:36 -0000, psteitz@apache.org wrote:
>>>>>
>>>>>> [...]
>>>>>
>>>>> I wonder whether the utility should involve the creation of
>>>>> an instance of a bona fide "Combination" class.
>>>>> I.e. instead of a "naked"
>>>>> Iterator<int[]> combinationIterator(int n, int k)
>>>>> there would be
>>>>> Iterator<Combination> combinationIterator(int n, int k)
>>>>> where "Combination" would provide an accessor
>>>>> public int[] toArray() {
>>>>> // ...
>>>>> }
>>>>
>>>> I need the "naked arrays" generated very quickly with minimal
>>>> overhead for the K-S use case.
>>>
>>> The only "overhead" would be the creation of an instance for
>>> wrapping the "int[]".
>>> [As allocation is fairly cheap in Java, that should not be a
>>> problem.]
>>>
>>>> My use case uses the arrays
>>>> directly, but others could use the indices to extract objects from
>>>> lists. For example, what I thought would be natural would be to
>>>> add
>>>> public static <T> Iterator<List<T>> combinationsIterator(List<T>
>>>> list, int k)
>>>
>>> Would this be the base implementation, from which your case would
>>> be implemented by retrieving "Integer" from the list and
>>> copy/convert
>>> them into an "int[]"?
>>
>> No, the opposite actually. The base impl is what exists now. It
>> works efficiently directly on an int[] array to compute the indices
>> within the source list (in my use case, {0, 1, ..., n-1} which is
>> actually canonical). Then if you want to source subsets of objects
>> from a list of objects, you can compute the int[] array that
>> actually *is* the combination and extract the corresponding elements
>> from the list.
>
> I got it.
>
>>>
>>>>
>>>> What you would get out of this is element lists. And the
>>>> implementation could postpone copy / creation until the indices
>>>> have
>>>> been selected using the existing method.
>>>
>>> I don't follow ...
>>
>> See above. I am probably still not explaining clearly what I have
>> in mind. To me, a "combination" is a subset of the integers {0,
>> ..., n-1}. Technically it is a set, not a list, but there is a
>> natural order available and enumeration can work easier if you use
>> that order and adopt the convention that you represent combinations
>> as ordered lists of integers. The LexicographicCombinationIterator
>> that I committed does that, using primitive arrays to represent the
>> lists. The iterator itself uses a primitive array of int[] to
>> maintain state and create successive iterates. Use of a single
>> primitive array eliminates all object creation / garbage collection,
>> which is not necessary to just enumerate the combinations. Once you
>> have a "true" combination represented as an array of int[], you can
>> use it to specify a "combination" (really sample or subset) of a
>> list of any kind of object.
>
> So, IIUC it would be useful to have a utility like
> -----
> public static List<T> getSample(List<T> elements,
> int[] combination) {
> final List<T> samples = new ArrayList<T>(combination.length);
> for (int index : combination) {
> samples.add(elements.get(index));
> }
> }
Yes, that is what the List version would use. Not sure how
generically useful it would be, but I can imagine other use cases.
It might be best to call it filter or subList or something and put
it in MathArrays. Not sure where it would belong as a generic utility.
> -----
>
>>>
>>>> I am not yet sold on the
>>>> value of "Combination" as an abstraction, since what you really
>>>> use
>>>> is just the list of selected elements.
>>>
>>> Maybe "Combination" is not worth implementing indeed; but what
>>> about
>>> a "Combinations" class:
>>>
>>> public class Combinations implements Iterable<int[]> {
>>> private final int n;
>>> private final int k;
>>>
>>> public Combinations(int n, int k) {
>>> // ...
>>> }
>>>
>>> public Iterator<int[]> iterator() {
>>> return new LexicographicCombinationIterator(n, k);
>>> }
>>>
>>> public Comparator<int[]> comparator() {
>>> return new LexicographicCombinationComparator(n, k);
>>> }
>>>
>>> private static class LexicographicCombinationIterator implements
>>> Iterator<int[]> {
>>> // [Your implementation]
>>> }
>>>
>>> private static class LexicographicCombinationComparator
>>> implements Comparator<int[]> {
>>> public int compare(int[], int[]) {
>>> // ... using e.g. "lexNorm" implementation.
>>> }
>>> }
>>> }
>>>
>>> Being "Iterable" allows nice usage in a "for" loop:
>>>
>>> for (int[] combination : new Combinations(4, 2)) {
>>> // ... etc.
>>> }
>>
>> I thought about that and that is what I meant by the original
>> suggestion that we possibly make the
>> LexicographicCombinationsIterator a public class. I just don't see
>> the practical use cases for it as a standalone class.
>
> The "for"-loop example above uses the iterator functionality but
> in a much less verbose way (no explicit calls to "hasNext()" and
> "next()").
> This is standard practice for everything that can be handled as a
> collection.
>
> Then, we can also have your iterator factory method:
> -----
> public static Iterator<int[]> combinationsIterator(int n, int k) {
> return new Combinations(4, 2).iterator();
> }
> -----
>
> Then, we also don't hide some code in "test" where it could be made
> visible and be used elsewhere (cf. "lexNorm").
OK, I see your point.
>
>> What I have
>> immediate practical need for is just a way to get an Iterator<int[]>
>> based on <n,k>. As you note above, it is the Iterator that is
>> useful. I can imagine use cases for the object-list version
>> public static <T> Iterator<List<T>> combinationsIterator(List<T>
>> list, int k ) though. If we do extract a public class, I would
>> prefer that it be called something like CombinationsIterator.
>
> I think that a design based on the "Iterable" interface is
> preferrable.
> From it you can always get the iterator functionality (by
> definition of
> the interface), while the reverse is not true.
Agreed.
>
>> If we
>> have other iteration strategies that we want to implement, we could
>> make it an abstract parent for LexicographicCombinationsIterator. I
>> would recommend holding off complicating the design / structure
>> though until we have these though.
>
> Sorry to insist but it is not a complication, it is a
> _simplification_ ;-)
> Instead of a specifically named method ("combinationsIterator"),
> we rely
> on the standard API ("Iterable") of the Java language.
Yeah, I get it now. Go for it or open a ticket so we don't forget.
Phil
>
>
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Improving combinationIterator?
Posted by Gilles <gi...@harfang.homelinux.org>.
On Sun, 25 Aug 2013 17:14:37 -0700, Phil Steitz wrote:
> On 8/25/13 9:59 AM, Gilles wrote:
>> On Sun, 25 Aug 2013 09:19:41 -0700, Phil Steitz wrote:
>>> On 8/25/13 8:10 AM, Gilles wrote:
>>>> On Sat, 24 Aug 2013 21:55:36 -0000, psteitz@apache.org wrote:
>>>>
>>>>> [...]
>>>>
>>>> I wonder whether the utility should involve the creation of
>>>> an instance of a bona fide "Combination" class.
>>>> I.e. instead of a "naked"
>>>> Iterator<int[]> combinationIterator(int n, int k)
>>>> there would be
>>>> Iterator<Combination> combinationIterator(int n, int k)
>>>> where "Combination" would provide an accessor
>>>> public int[] toArray() {
>>>> // ...
>>>> }
>>>
>>> I need the "naked arrays" generated very quickly with minimal
>>> overhead for the K-S use case.
>>
>> The only "overhead" would be the creation of an instance for
>> wrapping the "int[]".
>> [As allocation is fairly cheap in Java, that should not be a
>> problem.]
>>
>>> My use case uses the arrays
>>> directly, but others could use the indices to extract objects from
>>> lists. For example, what I thought would be natural would be to
>>> add
>>> public static <T> Iterator<List<T>> combinationsIterator(List<T>
>>> list, int k)
>>
>> Would this be the base implementation, from which your case would
>> be implemented by retrieving "Integer" from the list and
>> copy/convert
>> them into an "int[]"?
>
> No, the opposite actually. The base impl is what exists now. It
> works efficiently directly on an int[] array to compute the indices
> within the source list (in my use case, {0, 1, ..., n-1} which is
> actually canonical). Then if you want to source subsets of objects
> from a list of objects, you can compute the int[] array that
> actually *is* the combination and extract the corresponding elements
> from the list.
I got it.
>>
>>>
>>> What you would get out of this is element lists. And the
>>> implementation could postpone copy / creation until the indices
>>> have
>>> been selected using the existing method.
>>
>> I don't follow ...
>
> See above. I am probably still not explaining clearly what I have
> in mind. To me, a "combination" is a subset of the integers {0,
> ..., n-1}. Technically it is a set, not a list, but there is a
> natural order available and enumeration can work easier if you use
> that order and adopt the convention that you represent combinations
> as ordered lists of integers. The LexicographicCombinationIterator
> that I committed does that, using primitive arrays to represent the
> lists. The iterator itself uses a primitive array of int[] to
> maintain state and create successive iterates. Use of a single
> primitive array eliminates all object creation / garbage collection,
> which is not necessary to just enumerate the combinations. Once you
> have a "true" combination represented as an array of int[], you can
> use it to specify a "combination" (really sample or subset) of a
> list of any kind of object.
So, IIUC it would be useful to have a utility like
-----
public static List<T> getSample(List<T> elements,
int[] combination) {
final List<T> samples = new ArrayList<T>(combination.length);
for (int index : combination) {
samples.add(elements.get(index));
}
}
-----
>>
>>> I am not yet sold on the
>>> value of "Combination" as an abstraction, since what you really use
>>> is just the list of selected elements.
>>
>> Maybe "Combination" is not worth implementing indeed; but what about
>> a "Combinations" class:
>>
>> public class Combinations implements Iterable<int[]> {
>> private final int n;
>> private final int k;
>>
>> public Combinations(int n, int k) {
>> // ...
>> }
>>
>> public Iterator<int[]> iterator() {
>> return new LexicographicCombinationIterator(n, k);
>> }
>>
>> public Comparator<int[]> comparator() {
>> return new LexicographicCombinationComparator(n, k);
>> }
>>
>> private static class LexicographicCombinationIterator implements
>> Iterator<int[]> {
>> // [Your implementation]
>> }
>>
>> private static class LexicographicCombinationComparator
>> implements Comparator<int[]> {
>> public int compare(int[], int[]) {
>> // ... using e.g. "lexNorm" implementation.
>> }
>> }
>> }
>>
>> Being "Iterable" allows nice usage in a "for" loop:
>>
>> for (int[] combination : new Combinations(4, 2)) {
>> // ... etc.
>> }
>
> I thought about that and that is what I meant by the original
> suggestion that we possibly make the
> LexicographicCombinationsIterator a public class. I just don't see
> the practical use cases for it as a standalone class.
The "for"-loop example above uses the iterator functionality but
in a much less verbose way (no explicit calls to "hasNext()" and
"next()").
This is standard practice for everything that can be handled as a
collection.
Then, we can also have your iterator factory method:
-----
public static Iterator<int[]> combinationsIterator(int n, int k) {
return new Combinations(4, 2).iterator();
}
-----
Then, we also don't hide some code in "test" where it could be made
visible and be used elsewhere (cf. "lexNorm").
> What I have
> immediate practical need for is just a way to get an Iterator<int[]>
> based on <n,k>. As you note above, it is the Iterator that is
> useful. I can imagine use cases for the object-list version
> public static <T> Iterator<List<T>> combinationsIterator(List<T>
> list, int k ) though. If we do extract a public class, I would
> prefer that it be called something like CombinationsIterator.
I think that a design based on the "Iterable" interface is preferrable.
From it you can always get the iterator functionality (by definition of
the interface), while the reverse is not true.
> If we
> have other iteration strategies that we want to implement, we could
> make it an abstract parent for LexicographicCombinationsIterator. I
> would recommend holding off complicating the design / structure
> though until we have these though.
Sorry to insist but it is not a complication, it is a _simplification_
;-)
Instead of a specifically named method ("combinationsIterator"), we
rely
on the standard API ("Iterable") of the Java language.
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Improving combinationIterator?
Posted by Phil Steitz <ph...@gmail.com>.
On 8/25/13 9:59 AM, Gilles wrote:
> On Sun, 25 Aug 2013 09:19:41 -0700, Phil Steitz wrote:
>> On 8/25/13 8:10 AM, Gilles wrote:
>>> On Sat, 24 Aug 2013 21:55:36 -0000, psteitz@apache.org wrote:
>>>
>>>> [...]
>>>
>>> I wonder whether the utility should involve the creation of
>>> an instance of a bona fide "Combination" class.
>>> I.e. instead of a "naked"
>>> Iterator<int[]> combinationIterator(int n, int k)
>>> there would be
>>> Iterator<Combination> combinationIterator(int n, int k)
>>> where "Combination" would provide an accessor
>>> public int[] toArray() {
>>> // ...
>>> }
>>
>> I need the "naked arrays" generated very quickly with minimal
>> overhead for the K-S use case.
>
> The only "overhead" would be the creation of an instance for
> wrapping the "int[]".
> [As allocation is fairly cheap in Java, that should not be a
> problem.]
>
>> My use case uses the arrays
>> directly, but others could use the indices to extract objects from
>> lists. For example, what I thought would be natural would be to
>> add
>> public static <T> Iterator<List<T>> combinationsIterator(List<T>
>> list, int k)
>
> Would this be the base implementation, from which your case would
> be implemented by retrieving "Integer" from the list and copy/convert
> them into an "int[]"?
No, the opposite actually. The base impl is what exists now. It
works efficiently directly on an int[] array to compute the indices
within the source list (in my use case, {0, 1, ..., n-1} which is
actually canonical). Then if you want to source subsets of objects
from a list of objects, you can compute the int[] array that
actually *is* the combination and extract the corresponding elements
from the list.
>
>>
>> What you would get out of this is element lists. And the
>> implementation could postpone copy / creation until the indices have
>> been selected using the existing method.
>
> I don't follow ...
See above. I am probably still not explaining clearly what I have
in mind. To me, a "combination" is a subset of the integers {0,
..., n-1}. Technically it is a set, not a list, but there is a
natural order available and enumeration can work easier if you use
that order and adopt the convention that you represent combinations
as ordered lists of integers. The LexicographicCombinationIterator
that I committed does that, using primitive arrays to represent the
lists. The iterator itself uses a primitive array of int[] to
maintain state and create successive iterates. Use of a single
primitive array eliminates all object creation / garbage collection,
which is not necessary to just enumerate the combinations. Once you
have a "true" combination represented as an array of int[], you can
use it to specify a "combination" (really sample or subset) of a
list of any kind of object.
>
>> I am not yet sold on the
>> value of "Combination" as an abstraction, since what you really use
>> is just the list of selected elements.
>
> Maybe "Combination" is not worth implementing indeed; but what about
> a "Combinations" class:
>
> public class Combinations implements Iterable<int[]> {
> private final int n;
> private final int k;
>
> public Combinations(int n, int k) {
> // ...
> }
>
> public Iterator<int[]> iterator() {
> return new LexicographicCombinationIterator(n, k);
> }
>
> public Comparator<int[]> comparator() {
> return new LexicographicCombinationComparator(n, k);
> }
>
> private static class LexicographicCombinationIterator implements
> Iterator<int[]> {
> // [Your implementation]
> }
>
> private static class LexicographicCombinationComparator
> implements Comparator<int[]> {
> public int compare(int[], int[]) {
> // ... using e.g. "lexNorm" implementation.
> }
> }
> }
>
> Being "Iterable" allows nice usage in a "for" loop:
>
> for (int[] combination : new Combinations(4, 2)) {
> // ... etc.
> }
I thought about that and that is what I meant by the original
suggestion that we possibly make the
LexicographicCombinationsIterator a public class. I just don't see
the practical use cases for it as a standalone class. What I have
immediate practical need for is just a way to get an Iterator<int[]>
based on <n,k>. As you note above, it is the Iterator that is
useful. I can imagine use cases for the object-list version
public static <T> Iterator<List<T>> combinationsIterator(List<T>
list, int k ) though. If we do extract a public class, I would
prefer that it be called something like CombinationsIterator. If we
have other iteration strategies that we want to implement, we could
make it an abstract parent for LexicographicCombinationsIterator. I
would recommend holding off complicating the design / structure
though until we have these though.
Phil
>
>> [...]
>
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Improving combinationIterator?
Posted by Gilles <gi...@harfang.homelinux.org>.
On Sun, 25 Aug 2013 09:19:41 -0700, Phil Steitz wrote:
> On 8/25/13 8:10 AM, Gilles wrote:
>> On Sat, 24 Aug 2013 21:55:36 -0000, psteitz@apache.org wrote:
>>
>>> [...]
>>
>> I wonder whether the utility should involve the creation of
>> an instance of a bona fide "Combination" class.
>> I.e. instead of a "naked"
>> Iterator<int[]> combinationIterator(int n, int k)
>> there would be
>> Iterator<Combination> combinationIterator(int n, int k)
>> where "Combination" would provide an accessor
>> public int[] toArray() {
>> // ...
>> }
>
> I need the "naked arrays" generated very quickly with minimal
> overhead for the K-S use case.
The only "overhead" would be the creation of an instance for
wrapping the "int[]".
[As allocation is fairly cheap in Java, that should not be a
problem.]
> My use case uses the arrays
> directly, but others could use the indices to extract objects from
> lists. For example, what I thought would be natural would be to add
> public static <T> Iterator<List<T>> combinationsIterator(List<T>
> list, int k)
Would this be the base implementation, from which your case would
be implemented by retrieving "Integer" from the list and copy/convert
them into an "int[]"?
>
> What you would get out of this is element lists. And the
> implementation could postpone copy / creation until the indices have
> been selected using the existing method.
I don't follow ...
> I am not yet sold on the
> value of "Combination" as an abstraction, since what you really use
> is just the list of selected elements.
Maybe "Combination" is not worth implementing indeed; but what about
a "Combinations" class:
public class Combinations implements Iterable<int[]> {
private final int n;
private final int k;
public Combinations(int n, int k) {
// ...
}
public Iterator<int[]> iterator() {
return new LexicographicCombinationIterator(n, k);
}
public Comparator<int[]> comparator() {
return new LexicographicCombinationComparator(n, k);
}
private static class LexicographicCombinationIterator implements
Iterator<int[]> {
// [Your implementation]
}
private static class LexicographicCombinationComparator implements
Comparator<int[]> {
public int compare(int[], int[]) {
// ... using e.g. "lexNorm" implementation.
}
}
}
Being "Iterable" allows nice usage in a "for" loop:
for (int[] combination : new Combinations(4, 2)) {
// ... etc.
}
> [...]
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Improving combinationIterator? (Was: svn commit: r1517203
[2/2] - in /commons/proper/math/trunk/src: ...)
Posted by Phil Steitz <ph...@gmail.com>.
On 8/25/13 8:10 AM, Gilles wrote:
> On Sat, 24 Aug 2013 21:55:36 -0000, psteitz@apache.org wrote:
>
>> [...]
>
> I wonder whether the utility should involve the creation of
> an instance of a bona fide "Combination" class.
> I.e. instead of a "naked"
> Iterator<int[]> combinationIterator(int n, int k)
> there would be
> Iterator<Combination> combinationIterator(int n, int k)
> where "Combination" would provide an accessor
> public int[] toArray() {
> // ...
> }
I need the "naked arrays" generated very quickly with minimal
overhead for the K-S use case. My use case uses the arrays
directly, but others could use the indices to extract objects from
lists. For example, what I thought would be natural would be to add
public static <T> Iterator<List<T>> combinationsIterator(List<T>
list, int k)
What you would get out of this is element lists. And the
implementation could postpone copy / creation until the indices have
been selected using the existing method. I am not yet sold on the
value of "Combination" as an abstraction, since what you really use
is just the list of selected elements. Cf what [collections] did
for its PermutationIterator.
Phil
>
> The advantage is that "Combination" could also implement
> Comparable<Combination>
> with code similar to the "lexNorm" method defined for the tests.
>
> Or did I miss something?
>
>
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
[Math] Improving combinationIterator? (Was: svn commit: r1517203 [2/2] - in /commons/proper/math/trunk/src: ...)
Posted by Gilles <gi...@harfang.homelinux.org>.
On Sat, 24 Aug 2013 21:55:36 -0000, psteitz@apache.org wrote:
> [...]
I wonder whether the utility should involve the creation of
an instance of a bona fide "Combination" class.
I.e. instead of a "naked"
Iterator<int[]> combinationIterator(int n, int k)
there would be
Iterator<Combination> combinationIterator(int n, int k)
where "Combination" would provide an accessor
public int[] toArray() {
// ...
}
The advantage is that "Combination" could also implement
Comparable<Combination>
with code similar to the "lexNorm" method defined for the tests.
Or did I miss something?
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org