Combinations and Permutations in JavaScript

November 8, 2008 at 4:37 pm (JavaScript, Meta)
Tags: combinations, math, numbers, permutations, range

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) {
  if (n==k) {
    return 1;
  } else {
    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);
}

About these ads