A quick Google search for Java combination generators produces many results; nearly all focus on recursion (for more on recursion, see this post). While suitable for smaller sets, deep recursion quickly saturates the recursive stack, crashing Java. Thus, an iterative approach is warranted. In this post, both recursive and iterative approaches are shown.
Generate combinations
The recursive option begins with getCombinationsRecursive
, however generate
performs all the work. The iterative method is entirely contained within getCombinationsIterative
. This method produces all combinations from \(0…2^{|elements|}\), only processing those with \(k\) bits (line 57). While appearing to waste a good deal of time, the it is actually quite quick. Line 56 requires virtually no time to perform its task and line 57 executes only a handful of bitwise operations to compute the count. Therefore, in testing, the iterative method is roughly equal to that of recursive in time (assuming no garbage collector overhead for the recursive approach), yet requiring a much smaller memory footprint.
import java.util.List;
/**
* Generates a list of combinations for all subsets of size k.
* @author Ray Hylock
*/
public class Combinations {
/** This class should not be instantiated. */
private Combinations(){}
/**
* Generates all possible combinations using a recursive approach. The
* passed {@link List} {@code combos} is populated with the combinations.
* @param combos the list to populate
* @param elements the list of characters
* @param k k
*/
public static void getCombinationsRecursive(List<String> combos,
String elements, int k) {
generate(combos, "", elements.substring(0, elements.length()), k);
}
/**
* Generates the combinations.
* @param combos the list of combinations
* @param prefix the previous characters in the current combo
* @param elements the set of N elements
* @param k size of combination
*/
private static void generate(List<String> combos, String prefix,
String elements, int k) {
if (k == 0) {
combos.add(prefix);
return;
}
for (int i = 0; i < elements.length(); i++) {
generate(combos, prefix + elements.charAt(i),
elements.substring(i + 1), k - 1);
}
}
/**
* Generates all possible combinations using an iterative approach. The
* passed {@link List} {@code combos} is populated with the combinations.
* @param combos the list to populate
* @param elements the list of characters
* @param k size of combination
*/
public static void getCombinationsIterative(List<String> combos,
String elements, int k){
int len = elements.length();
char[] e = elements.toCharArray();
long combinations = 1L << len;
StringBuilder sb = new StringBuilder();
// reverse combinations and left->right = alphabetical sorting
for(long i=combinations-1; i>=0; i--){ // reverse combinations
if (Long.bitCount(i) == k) {
sb.setLength(0); // reset
// left->right and ajust non-zero offsets
for (int j=len-1; j>=0; j--) {
if ((i & (1 << j)) != 0) sb.append(e[len-j-1]);
}
combos.add(sb.toString());
}
}
}
}
The following is an example calling class.
public class CombinationsTest {
List<String> combos = new ArrayList<String>();
String elements = "abcdefg";
int k = 3;
boolean print = true;
// recursive
System.out.println("Recursive");
Combinations.getCombinationsRecursive(combos, elements, k);
if(print) for(String s : combos) System.out.println(s);
// iterative
combos.clear();
System.out.println("\nIterative");
Combinations.getCombinationsIterative(combos, elements, k);
if(print) for(String s : combos) System.out.println(s);
}
}
Output for this example:
Recursive
abc
abd
abe
abf
abg
acd
ace
acf
acg
ade
adf
adg