June 23, 2017 Generating Combinations

This week I’d like to share my favorite methods for generating combinations of elements. Combinations are O(2^n) so we generally only use them when there are less than 100 elements. However, this technique can give us a confidence because it is simple and we can, in essence, check every possible solution to be sure we’ve got the best one.
So there are two possible solutions that I know of for generating combinations – recursive and iterative. My favorite is the iterative because it uses a really neat trick, but I’ll start with explaining the elegant recursive solution.

The Recursive Method

In this method, we go through each element and either (a) not put it in the set or (b) put it in the set. Now every time we reach the last element we have generated a new combination! Simple? Let’s see it in Golang code:

    func recursive_combinations(elems []elements, combination []elements, ndx int) {
        if ndx == len(elems) {
            // (reached end of list after selecting/not selecting)
            fmt.Println(combination)
        } else {
            // (element at ndx not included)
            recursive_combinations(elems, combination, ndx+1)
            // (include element at ndx)
            recursive_combinations(elems, append(combination,elems[ndx]), ndx+1)
        }
    }

The Iterative Method

Now for my favorite method. I love this because it uses a little trick – think about the elements “standing” one next to the other. Under it we imagine a little switch – “on” if the element is in the set, “off” if it isn’t:

On…off…on…off… sounds familiar? It “looks like” the binary representation of a number. And what I find so delightful is that – yes – we can use the binary representation of a number to generate all possible combinations! All the numbers from 0 to (2^n-1) contain, in them, all the combinations we need! This is simple and neat to code:

    func iterate_combinations(elems []elements) {
        n := len(elems)
        for num:=0;num < (1 << uint(n));num++ {
            combination := []elements{}
            for ndx:=0;ndx<n;ndx++ {
                // (is the bit "on" in this number?)
                if num & (1 << uint(ndx)) != 0 {
                    // (then add it to the combination)
                    combination = append(combination, elems[ndx])
                }
            }
            fmt.Println(combination)
        }
    }

I hope you like these little tricks and it helps you out sometime! Catch you next week!