0

In my application, I need all subsets of a given size k of an array 1..n.

This could easily be done using a recursive approach and storing all found subsets along the way. However, I don't want my application to use an exponential amount of memory [O(n^k)].

Therefore, I want to write a class that implements (Java's) Iterator to iterate over said subsets.

public class SubsetIterator implements Iterator<int[]> {

    private int k;
    private int[] array;

    public SubsetIterator(int k, int[] array) {
        this.k     = k;
        this.array = array;
    }

    @Override
    public boolean hasNext() {
        //To be implemented.
    }

    @Override
    public int[] next() {
        //To be implemented.
    }
}

So I can use it as follows:

SubsetIterator iter = new SubsetIterator(k, array);

while (iter.hasNext) {
    int[] next = iter.next();
    //Do stuff
}

Obviously we will need to store the current subset last returned by next() which is initialized as 1..k. But how could one compute the next subset from this current subset?

Auberon
  • 665
  • 2
  • 7
  • 23
  • Exactly the same thing done by many people before, and me too. Please check `hasNext()` method [here](https://github.com/Salauyou/Java-Utils/blob/master/src/main/java/ru/salauyou/util/misc/KCombinationIterator.java#L94) – Alex Salauyou Apr 04 '16 at 12:58

1 Answers1

0

I think you should go with the approach of storing all of the subsets, if that is possible for your use case. Otherwise you will allocate the same amount of memory every time you use iterator which will make the GC work pretty hard.

gustf
  • 1,959
  • 13
  • 20