Combinations and Permutations in JavaScript

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);
}
Advertisements

In Which I Discover I’m More Interesting and Provocative in Spanish

Some terrific Spanish-speaking people linked to this blog. Thanks to all those English-as-a-second-language readers out there who take the time to work through a blog like mine.

Google’s delightful Spanish-to-English translation…

Dreaming in Javascript

The more I write JavaScript, but I’m sure thinking that the language domain. Just when I decide one way to do something, I can think of another way of doing amazingly better.

JavaScript is a language that seems to have grown up with the sun shining on him. While Java is the caretaker of the beach, blonde boat and surrounded by plastic boobs embobados, JavaScript is disturbingly mysterious maiden forest that you can barely glimpse for a moment while you open passage between blackberries and brambles.

Two assertions of the most intriguing blog Dreaming in Javascript. Undoubtedly he invented the word recommended.

They are quoting from The Object Slinger post. Who knew I had such a flair for writing in Spanish?