Post | mennovanslooten.nl/blog

An email sent by a reader of my previous post about combinatorics renewed my interest in the subject. As I wrote in that particular post I didn't really understand why the code did what it did. It was actually the result of an almost evolutionary process of trial and error until I was confident it did what it should do.

Another method

A reader called Fabrice pointed out another way to get the same results using bitmasks. For example, when you want to get all the combinations of items from [0,1,2] you create a list binary representations of the numbers 1 to (2³-1):

1. 001
2. 010
3. 011
4. 100
5. 101
6. 110
7. 111

Applying each of these numbers as a mask to the original array gives us all the combinations:

1. 001 × [0,1,2] = [2]
2. 010 × [0,1,2] = [1]
3. 011 × [0,1,2] = [1,2]
4. 100 × [0,1,2] = [0]
5. 101 × [0,1,2] = [0,2]
6. 110 × [0,1,2] = [0,1]
7. 111 × [0,1,2] = [0,1,2]

It's a very simple algorithm to understand and to implement. Since this returns all possible combinations the only thing left is filtering for results of a certain length. Here's an implementation in JavaScript as an extension on the array prototype:

Array.prototype.combinate2 = function( length ) {
    var result = [];
    // iterate from 1 to 2n
    for (var i = 1; i < Math.pow(2, this.length) - 1; i++) {
         var combination = [];
         // For each value of i, check the individual 'bits' (powers of 2
         // components). If 2m is a component of i then this[m] is a
         // part of this combination
         for (var j = 0; j < i; j++) {
             var mask = Math.pow(2,j);
             if (i & mask) {
                 combination.push(this[j]);
             }
         }
         if (combination.length === length) {
             result.push(combination);
         }
    }
    
    return result;
}

Performance problems

Unfortunately, the simplicity of the algorithm comes with a price: the time it takes to execute increases much more quickly with the length of the array than the other one. If I knew something about big O-notation I could probably write something profound about why this is the case. It's a shame I don't because I feel it would really help understanding stuff like this. On the other hand, after having taken another look at the code from the original post I now fully understand what it does. Perhaps I will dedicate another post to that subject.