In JavaScript Numbers Can Bite, I talked about a problem that can crop up in JavaScript when you’re doing calculations with integers.
At the end of the post I hinted at a better way to write the combination function. Let’s go ahead and implement it. I’ll throw a permutation function in as well.
Let’s look at combinations. The formula is:
n!/(k!*(n-k)!)
That’s for n items, taken k at a time. In my mom’s family, there were seven children. How many combinations of them are there if you take 4 at a time?
7!/(4!*3!)
Now, if we write out the factorials, we immediately see a simplification (not in notation, but in floating point operations).
(7*6*5*4*3*2*1)/(4*3*2*1*3*2*1) = (7*6*5)/(3*2*1)
What we need here is a function that multiplies a range of numbers. Then we have:
productRange(5,7)/productRange(1,3)
or more generally,
productRange(k+1,n)/productRange(1,n-k)
function productRange(a,b) {
var product=a,i=a;
while (i++<b) {
product*=i;
}
return product;
}
function combinations(n,k) {
k=Math.max(k,n-k);
return productRange(k+1,n)/productRange(1,n-k);
}
So that’s combinations, where the order of the items doesn’t matter. What about permutations, where the order does matter? The formula is:
n!/(n-k)!
That one is simple…
function permutations(n,k) {
return productRange(k+1,n);
}
TNO said,
November 8, 2008 at 5:46 pm
Math.max can be slow, it’s more efficient to use the inline if statement:
k=(k < n-k) ? n-k : k;
Nosredna said,
November 8, 2008 at 6:04 pm
Really? Good to know. I would have thought that a built-in library function would be quick. Maybe it’s doing a lot of type checking?
It probably depends on the browser.
TNO said,
November 8, 2008 at 6:26 pm
Operators are always faster than method calls since there is no lookup involved
Nosredna said,
November 8, 2008 at 7:26 pm
Note that that line could be done away with.
Paul Hanlon said,
November 9, 2008 at 6:25 am
Hi Nosredna,
Very elegant. I love algorithms that reduce complexity, and in so doing, run faster.
Nice site too. Learned a pile!
Paul