commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gilles <gil...@harfang.homelinux.org>
Subject Re: [Math] Improving combinationIterator?
Date Sun, 25 Aug 2013 16:59:32 GMT
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


Mime
View raw message