You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Phil Steitz <ph...@gmail.com> on 2013/08/20 17:51:30 UTC
[math] enumerating combinations
The monte carlo approach I developed for 2-sample Kolmogorov-Smirnov
tests converges too slowly to be practical. I suspect full
enumeration of n - m partitions of n + m will actually be faster for
small m + n. To do this, I need to enumerate combinations. I have
implemented a fast, non-recursive algorithm to do this (Knuth's
algorithm T from 7.2.1.3 of TACP 4A), exposed as
class LexicographicCombinationIterator implements Iterator<int[]>
The constructor takes <n, k> and the int[] arrays returned by next()
are increasing k-length arrays from {0, ..., n - 1}, iterated in
lexicographic order. The array-based approach is what I need in K-S
and also fastest.
Initially, I implemented this as a private inner class in
KolmogorovSmirnovTest, but this is making testing inconvenient and
it also seems like a generically useful class. The question is
where to put it. One possibility is to make it a public inner class
of MathArrays. Of just add it as a class in util. Advice appreciated.
Phil
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] enumerating combinations
Posted by Ajo Fod <aj...@gmail.com>.
I feel like it belongs in a separate class in utils.
-Ajo
On Tue, Aug 20, 2013 at 12:24 PM, Phil Steitz <ph...@gmail.com> wrote:
> On 8/20/13 12:09 PM, Ajo Fod wrote:
> > I think it belongs in stat.inference. That is where all the tests are.
>
> Sorry, I should have been more clear. I intend to put
> KolmogorovSmirnovTest in stat.inference. I agree it belongs there.
> What I am puzzling over is where to put the combinations iterator.
>
> Phil
> >
> > -Ajo
> >
> >
> > On Tue, Aug 20, 2013 at 8:51 AM, Phil Steitz <ph...@gmail.com>
> wrote:
> >
> >> The monte carlo approach I developed for 2-sample Kolmogorov-Smirnov
> >> tests converges too slowly to be practical. I suspect full
> >> enumeration of n - m partitions of n + m will actually be faster for
> >> small m + n. To do this, I need to enumerate combinations. I have
> >> implemented a fast, non-recursive algorithm to do this (Knuth's
> >> algorithm T from 7.2.1.3 of TACP 4A), exposed as
> >>
> >> class LexicographicCombinationIterator implements Iterator<int[]>
> >>
> >> The constructor takes <n, k> and the int[] arrays returned by next()
> >> are increasing k-length arrays from {0, ..., n - 1}, iterated in
> >> lexicographic order. The array-based approach is what I need in K-S
> >> and also fastest.
> >>
> >> Initially, I implemented this as a private inner class in
> >> KolmogorovSmirnovTest, but this is making testing inconvenient and
> >> it also seems like a generically useful class. The question is
> >> where to put it. One possibility is to make it a public inner class
> >> of MathArrays. Of just add it as a class in util. Advice appreciated.
> >>
> >> Phil
> >>
> >> ---------------------------------------------------------------------
> >> 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] enumerating combinations
Posted by Phil Steitz <ph...@gmail.com>.
On 8/20/13 12:09 PM, Ajo Fod wrote:
> I think it belongs in stat.inference. That is where all the tests are.
Sorry, I should have been more clear. I intend to put
KolmogorovSmirnovTest in stat.inference. I agree it belongs there.
What I am puzzling over is where to put the combinations iterator.
Phil
>
> -Ajo
>
>
> On Tue, Aug 20, 2013 at 8:51 AM, Phil Steitz <ph...@gmail.com> wrote:
>
>> The monte carlo approach I developed for 2-sample Kolmogorov-Smirnov
>> tests converges too slowly to be practical. I suspect full
>> enumeration of n - m partitions of n + m will actually be faster for
>> small m + n. To do this, I need to enumerate combinations. I have
>> implemented a fast, non-recursive algorithm to do this (Knuth's
>> algorithm T from 7.2.1.3 of TACP 4A), exposed as
>>
>> class LexicographicCombinationIterator implements Iterator<int[]>
>>
>> The constructor takes <n, k> and the int[] arrays returned by next()
>> are increasing k-length arrays from {0, ..., n - 1}, iterated in
>> lexicographic order. The array-based approach is what I need in K-S
>> and also fastest.
>>
>> Initially, I implemented this as a private inner class in
>> KolmogorovSmirnovTest, but this is making testing inconvenient and
>> it also seems like a generically useful class. The question is
>> where to put it. One possibility is to make it a public inner class
>> of MathArrays. Of just add it as a class in util. Advice appreciated.
>>
>> Phil
>>
>> ---------------------------------------------------------------------
>> 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] enumerating combinations
Posted by Ajo Fod <aj...@gmail.com>.
I think it belongs in stat.inference. That is where all the tests are.
-Ajo
On Tue, Aug 20, 2013 at 8:51 AM, Phil Steitz <ph...@gmail.com> wrote:
> The monte carlo approach I developed for 2-sample Kolmogorov-Smirnov
> tests converges too slowly to be practical. I suspect full
> enumeration of n - m partitions of n + m will actually be faster for
> small m + n. To do this, I need to enumerate combinations. I have
> implemented a fast, non-recursive algorithm to do this (Knuth's
> algorithm T from 7.2.1.3 of TACP 4A), exposed as
>
> class LexicographicCombinationIterator implements Iterator<int[]>
>
> The constructor takes <n, k> and the int[] arrays returned by next()
> are increasing k-length arrays from {0, ..., n - 1}, iterated in
> lexicographic order. The array-based approach is what I need in K-S
> and also fastest.
>
> Initially, I implemented this as a private inner class in
> KolmogorovSmirnovTest, but this is making testing inconvenient and
> it also seems like a generically useful class. The question is
> where to put it. One possibility is to make it a public inner class
> of MathArrays. Of just add it as a class in util. Advice appreciated.
>
> Phil
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Re: [math] enumerating combinations
Posted by James Carman <ja...@carmanconsulting.com>.
On Tue, Aug 20, 2013 at 9:29 PM, Phil Steitz <ph...@gmail.com> wrote:
>
> But what is returned by the iterator is arrays and there is no
> "arithmetic" going on. One thing I did think of was cutting out the
> binomial coefficients from "ArithmeticUtils" and creating a
> Combinatorics or CombinatoricsUtils class within utils.
>
CombinatoricsUtils sounds right here. +1
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] enumerating combinations
Posted by Gilles <gi...@harfang.homelinux.org>.
>> [...]
>>
>> "ArithmeticUtils" seems appropriate.
>
> But what is returned by the iterator is arrays and there is no
> "arithmetic" going on. One thing I did think of was cutting out the
> binomial coefficients from "ArithmeticUtils" and creating a
> Combinatorics or CombinatoricsUtils class within utils.
That makes sense indeed.
+1 for "CombinatoricsUtils" in "o.a.c.m.util".
Gilles
> [...]
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] enumerating combinations
Posted by Phil Steitz <ph...@gmail.com>.
On 8/20/13 6:04 PM, Gilles wrote:
> On Tue, 20 Aug 2013 08:51:30 -0700, Phil Steitz wrote:
>> The monte carlo approach I developed for 2-sample Kolmogorov-Smirnov
>> tests converges too slowly to be practical. I suspect full
>> enumeration of n - m partitions of n + m will actually be faster for
>> small m + n. To do this, I need to enumerate combinations. I have
>> implemented a fast, non-recursive algorithm to do this (Knuth's
>> algorithm T from 7.2.1.3 of TACP 4A), exposed as
>>
>> class LexicographicCombinationIterator implements Iterator<int[]>
>>
>> The constructor takes <n, k> and the int[] arrays returned by next()
>> are increasing k-length arrays from {0, ..., n - 1}, iterated in
>> lexicographic order. The array-based approach is what I need in K-S
>> and also fastest.
>>
>> Initially, I implemented this as a private inner class in
>> KolmogorovSmirnovTest, but this is making testing inconvenient and
>> it also seems like a generically useful class. The question is
>> where to put it. One possibility is to make it a public inner class
>> of MathArrays. Of just add it as a class in util. Advice
>> appreciated.
>
> "ArithmeticUtils" seems appropriate.
But what is returned by the iterator is arrays and there is no
"arithmetic" going on. One thing I did think of was cutting out the
binomial coefficients from "ArithmeticUtils" and creating a
Combinatorics or CombinatoricsUtils class within utils.
What I have in my local checkout now is the iterator itself defined
as a static inner class in MathArrays and
public static Iterator<int[]> combinationsIterator(int n, int k)
using it. Convenience methods could also be added there to use the
straight array-based impl to source combinations from Collections or
source arrays.
The right question to ask is where would someone think to look for
this functionality. Unfortunately, neither MathArrays nor
ArithmeticUtils really makes sense. So I am thinking now that just
making the iterator itself a top level class or creating
CombinatoricsUtils would be best.
Phil
>
> Gilles
>
>>
>> Phil
>>
>> ---------------------------------------------------------------------
>>
>> 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] enumerating combinations
Posted by Gilles <gi...@harfang.homelinux.org>.
On Tue, 20 Aug 2013 08:51:30 -0700, Phil Steitz wrote:
> The monte carlo approach I developed for 2-sample Kolmogorov-Smirnov
> tests converges too slowly to be practical. I suspect full
> enumeration of n - m partitions of n + m will actually be faster for
> small m + n. To do this, I need to enumerate combinations. I have
> implemented a fast, non-recursive algorithm to do this (Knuth's
> algorithm T from 7.2.1.3 of TACP 4A), exposed as
>
> class LexicographicCombinationIterator implements Iterator<int[]>
>
> The constructor takes <n, k> and the int[] arrays returned by next()
> are increasing k-length arrays from {0, ..., n - 1}, iterated in
> lexicographic order. The array-based approach is what I need in K-S
> and also fastest.
>
> Initially, I implemented this as a private inner class in
> KolmogorovSmirnovTest, but this is making testing inconvenient and
> it also seems like a generically useful class. The question is
> where to put it. One possibility is to make it a public inner class
> of MathArrays. Of just add it as a class in util. Advice
> appreciated.
"ArithmeticUtils" seems appropriate.
Gilles
>
> Phil
>
> ---------------------------------------------------------------------
> 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