Post | mennovanslooten.nl/blog

Some years ago I had combinatorics in high school. I don't remember many specifics apart from that it had a lot to do with permutations and seemed to center around the problem: how many ways are there of picking k objects from a set of n?. For a personal project of mine I had to create a JavaScript function that solved this problem for Arrays.

Actually, the problem of how many possibilities there are is quite simple since there's a formula. For k items out of a set of n there are n! / ( k! * (n - k)!) possibilities. Actually getting the possibilities turned out to be quite a task for me, though.

In the end, however, I seemed to have cracked it (I was surprised after much googling there seemed to be no prior solution, which I find hard to believe). The solution I ended up with is this:

Array.prototype.combinate = function( iItems, aIn ) {
    if (!aIn) {
        var aIn = new Array();
        this.combinate.aResult = new Array();
    }
    
    for(var i = 0; i < this.length; i++) {
        var a = aIn.concat(this[i]);
        var aRest = this.concat(); // Concat with nothing to create copy
        aRest.splice(0, i + 1);
        
        if(iItems && iItems - 1 <= aRest.length) {
            aRest.combinate(iItems - 1, a);
            if(iItems == 1) this.combinate.aResult.push(a);
        }
    }
    
    return this.combinate.aResult;
}

Which can be used like this:

// Create an array
var a = [0,1,2,3];

// Get all possible combinations of 2 items from a
var b = a.combinate(2);
// b = [[0, 1] [0, 2] [0, 3] [1, 2] [1, 3] [2, 3]]

By the way, don't ask me how it works. I don't really know. It just does. In short: it recursively walks down all possibilities of combining the current item (this[i]) with the rest (aRest.splice(0, i + 1)). Whenever a combination reaches the intended length (iItems == 1) it appends it to the result array.

Some issues

There are a couple of issues with my method however:

• I'm not at all happy with the this.combinate.aResult variable (which I suppose I should clean up before I return it). It just seems like this loose thread hanging.
• Another one is aRest = this.concat() bit to create a quick copy of an array. I think it's rather nifty but looks too much like a hack.
• The method name combinate() just seems...wrong

All in all however I'm quite pleased. This bugger's been driving me nuts for almost a week now and I really needed it to get on with my project. Maybe I'll write something about that later on. In the meantime, feel free to test the code here.