Long after my babbling on permutations before, here is a similar class on combinations.
import java.util.BitSet;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
/**
*
* All combinations of the given list. Does not use recursion and utilizes a
* BitSet structure to determine the lexicographic order of items
*
* @param <T> type of items
*/
public class Combinations<T> implements Iterable<List<T>> {
/**
* @param <T> type of items
* @param list list of items to combine
* @return all possible combinations
*/
public static <T> Stream<List<T>> all(final List<T> list) {
return IntStream.range(1, list.size() + 1)
.mapToObj(i -> new Combinations<>(list, i))
.map(i -> StreamSupport.stream(i.spliterator(), false))
.flatMap(i -> i);
}
private final BitSet bits;
private final List<T> items;
private Combinations(final List<T> items, final int num) {
this.items = items;
this.bits = new BitSet(items.size());
this.bits.set(items.size() - num, items.size()); // this creates the
// first combination
}
@Override
public Iterator<List<T>> iterator() {
return new Iterator<>() {
// the iterator pre-computes the next item because there is always a
// first item.
private BitSet bitsIt = (BitSet) Combinations.this.bits.clone();
private List<T> combinedItems(final BitSet result) {
return result.stream()
.mapToObj(Combinations.this.items::get)
.collect(Collectors.toList());
}
private void computeNext() {
int pos = Combinations.this.items.size() - 1;
while (pos > 0
&& !(this.bitsIt.get(pos) && !this.bitsIt.get(pos - 1))) {
pos--;
}
if (pos == 0) {
this.bitsIt = null;
} else {
this.bitsIt.set(pos - 1);
final int rest = this.bitsIt
.get(pos + 1, Combinations.this.items.size())
.cardinality();
this.bitsIt.clear(pos,
Combinations.this.items.size() - rest);
this.bitsIt.set(Combinations.this.items.size() - rest,
Combinations.this.items.size());
}
}
@Override
public boolean hasNext() {
return this.bitsIt != null;
}
@Override
public List<T> next() {
if (!this.hasNext()) {
throw new NoSuchElementException();
}
final BitSet result = (BitSet) this.bitsIt.clone();
this.computeNext();
return this.combinedItems(result);
}
};
}
}