迭代器遍歷給定大小的所有子集

在我的應用程序中，我需要數組k的給定大小的所有子集。迭代器遍歷給定大小的所有子集

這可以很容易地使用遞歸方法完成，並沿途存儲所有找到的子集。但是，我不希望我的應用程序使用指數量的內存[O（n^k）]。

因此，我想編寫一個實現（Java）Iterator的類來遍歷所述子集。

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. 
    } 
}

因此，我可以按如下方式使用它：

SubsetIterator iter = new SubsetIterator(k, array); 

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

顯然，我們需要存儲由next()上次返回當前的子集被初始化爲1..k。但是，如何從這個當前子集計算下一個子集呢？

來源

2016-04-04 Auberon

以前和我一樣，很多人完成了同樣的事情。請檢查'hasNext（）'方法[這裏]（https://github.com/Salauyou/Java-Utils/blob/master/src/main/java/ru/salauyou/util/misc/KCombinationIterator.java#L94） –

我認爲你應該採用存儲所有子集的方法，如果這對你的用例是可能的。否則，每次使用迭代器時都會分配相同數量的內存，這會使GC工作非常困難。

來源

2016-04-04 12:57:54 gustf

迭代器遍歷給定大小的所有子集

回答

相關問題