Combinations

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