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-unsubscr...@commons.apache.org
>> For additional commands, e-mail: dev-h...@commons.apache.org
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
