Generating Combinations

June 23, 2017 clobo

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)
        } 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])

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

The post Generating Combinations appeared first on Topcoder.

Previous Article
TCO17 Beijing Regionals
TCO17 Beijing Regionals

After an all amazing last year TCO16 Beijing Regionals we were very excited to go back and do an event in.....

Next Article
Get to Know Topcoder CEO Mike Morris on Talking Cities Podcast
Get to Know Topcoder CEO Mike Morris on Talking Cities Podcast

How did Topcoder get started? Why use gamification to build a crowdsourcing community? How do businesses us...