(See the next iteration.)
Given a positive \$N\$, the following class generates all possible non-empty sets \$A \in \mathcal{P}(\{0, 1, \dots, N - 1\})\$ in lexicographic order. Also, it provides a method that can be used to copy a combination to a list. I am seeking primarily guidance regarding the API design of the class.
CombinationGenerator.java:
package net.coderodde.util;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
public class CombinationGenerator<T> {
/**
* The array holding indices to elements considered to be in a combination.
* Only the first {@code k} indices are considered actually to encode an
* item in a combination.
*/
private final int[] indexArray;
/**
* The current number of items in a combination.
*/
private int k;
public CombinationGenerator(int totalNumberOfItems) {
checkTotalNumberOfItems(totalNumberOfItems);
this.indexArray = new int[totalNumberOfItems];
}
public boolean generateNextCombination() {
if (k == 0) {
k = 1;
return true;
}
if (indexArray[k - 1] < indexArray.length - 1) {
indexArray[k - 1]++;
return true;
}
for (int i = k - 2; i >= 0; --i) {
if (indexArray[i] < indexArray[i + 1] - 1) {
indexArray[i]++;
for (int j = i + 1; j < k; ++j) {
indexArray[j] = indexArray[j - 1] + 1;
}
return true;
}
}
++k;
if (k > indexArray.length) {
return false;
}
for (int i = 0; i < k; ++i) {
indexArray[i] = i;
}
return true;
}
public void loadCombination(List<T> all, List<T> target) {
Objects.requireNonNull(all, "The list being sampled is null.");
Objects.requireNonNull(target,
"The list to hold the combination is null.");
target.clear();
for (int i = 0; i < k; ++i) {
target.add(all.get(indexArray[i]));
}
}
private void checkTotalNumberOfItems(int totalNumberOfItems) {
if (totalNumberOfItems < 1) {
throw new IllegalArgumentException(
"Total number of items is illegal: " +
totalNumberOfItems + ".");
}
}
public static void main(final String... args) {
List<String> all = new ArrayList<>();
all.add("A");
all.add("B");
all.add("C");
all.add("D");
all.add("E");
int row = 1;
List<String> combinationHolder = new ArrayList<>();
CombinationGenerator generator = new CombinationGenerator(all.size());
while (generator.generateNextCombination()) {
generator.loadCombination(all, combinationHolder);
System.out.printf("%2d: %s\n", row++, combinationHolder);
}
}
}
CombinationGeneratorTest.java:
package net.coderodde.util;
import java.util.ArrayList;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;
public class CombinationGeneratorTest {
private CombinationGenerator generator;
@Test
public void test() {
List<String> all = new ArrayList<>();
List<String> target = new ArrayList<>();
all.add("A");
all.add("B");
all.add("C");
all.add("D");
all.add("E");
for (int i = 1; i <= all.size(); ++i) {
int combinations = pow2(i) - 1;
int count = 0;
generator = new CombinationGenerator(i);
while (generator.generateNextCombination()) {
count++;
}
assertEquals(combinations, count);
}
}
private static int pow2(int exp) {
return 1 << exp;
}
}