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, [email protected] 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: [email protected]
> For additional commands, e-mail: [email protected]
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
