Depth First Search

Enumerate k-Combination

Given a list of n elements, how to enumerate all combinations of k elements.

Different from the permutation, we don't care the order of the elements. Denote the list as {x1 , x2 , ..., xn}. Start from the first element x1, we can either pick it or not to form the result.

• If x1 is selected, we can next recursively enumerate k-1 out of the rest n-1 elements; By adding x1 to each of the combination of k-1 elements, we can get a result of length k;
• Otherwise, we skip x1, and recursively enumerate k out of the rest n-1 elements;

Put the above 2 cases together, we can generate all the combinations with and without x1. In order to terminate the recursion, we need figure out the edge cases. There are 3 in total:

• Enumerate combinations of 0 elements always yields empty result;
• If r > n, enumerate combination of r elements yields empty result;
• if r = 1, the result is n combinations. They are {{x1}, {x2}, ..., {xn}}.

Summarize all these together, we can develop a solution as below example Haskell code.

comb _  0 = []
comb xs 1 = [[x] | x <- xs]
comb xs@(x:xs') r | length xs < r = []
                  | otherwise = [x:ys | ys <- comb xs' (r-1)] ++ comb xs' r

If we want to eliminate the recursion to develop a purely imperative solution, we can use the depth-first search approach. We maintain a stack of states. Each state contains a list of selected elements so far like xs = {xp, xq, ..., xm} , and a number i which records how many elements we've examined. Every time, we pop a state from the stack. If the length of xs is r (|xs| = r), it means we find a solution, we record it and continue; Otherwsie, unless the length of xs is less than r, and i indicates that there are still elements we haven't examined, we have two options:

• We can either select the next element to i, to form a new candidate xs' = {xp, xq, ..., xm, xj}, where j = i+1; then push xs' and j as a new state to the stack;
• Or skip the next element, and go on searching. For this, we keep xs unchanged, and increase i to i+1 as the new state. Then push them back to the stack.

When the stack is empty, we've examined all the possible candidates. At this time, we can return the recorded combinations as the final result.

Below Java example code illustrates this solution.

static class Tuple {
    List<Integer> xs;
    int i;

    Tuple(List<Integer> xs, int i) {
        this.xs = xs;
        this.i = i;
    }
}

public static <T> List<List<T>> comb(final List<T> xs, final int r) {
    List<List<T>> res = new ArrayList<>();
    if (xs.size() < r || r <= 0) { return res; }
    Stack<Tuple> stack = new Stack<>();
    stack.push(new Tuple(Collections.emptyList(), 0));
    while(!stack.empty()) {
        Tuple t = stack.pop();
        if (t.xs.size() == r) {
            res.add(t.xs.stream().map(i -> xs.get(i)).collect(Collectors.toList()));
        } else if (t.xs.size() < r && t.i < xs.size()) {
            List<Integer> ys = new ArrayList<>(t.xs);
            ys.add(t.i++);
            stack.push(new Tuple(ys, t.i));
            stack.push(new Tuple(new ArrayList<>(t.xs), t.i));
        }
    }
    Collections.reverse(res);
    return res;
}

With recursion, there is another approach. When picking the elements from xs to form a combination ys, we start from the empty ys. There are n options to choose the first element, from x1, x2, to xn. For each option xj, we record the selection j, then current combination candiate ys = xj, then go on choosing the second elements. This time, we have n - j options, from the j+1 th to the n th. (We need skip the first j elements as they were processed.) Everytime when the length of the candidate ys is r, we find a solution. We can record it in an accumulator. After examine all the possible solution, we can return the accumulator as the final result.

Below Python example program shows this solution:

def comb(xs, r):
    n = len(xs)
    acc = []
    def dfs(i, ys):
        if len(ys) == r:
            acc.append(ys)
        else:
            for j in range(i, n):
                dfs(j + 1, ys + [xs[j]])
    dfs(0, [])
    return acc

The relative Java example can be found here: https://github.com/liuxinyu95/AlgoXY/blob/algoxy/others/appendix/list/src/Comb.java#L38

End.