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);
}
About these ads

13 Comments

  1. 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;

  2. 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.

  3. TNO said,

    November 8, 2008 at 6:26 pm

    Operators are always faster than method calls since there is no lookup involved

  4. Nosredna said,

    November 8, 2008 at 7:26 pm

    Note that that line could be done away with.

  5. 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

  6. ken larkin said,

    July 9, 2009 at 10:07 am

    This formula is incorrect, if you have 7 in your family you have only one combination of seven. This formula returns 8 for combinations(7,7)

  7. Nosredna said,

    April 13, 2010 at 8:53 pm

    ken, obviously I suck. I’ll take a look and see what I did wrong. I hope you’ve read my disclaimer:

    http://dreaminginjavascript.wordpress.com/about/

  8. Nosredna said,

    April 14, 2010 at 1:30 am

    Oh. I bet it’s because zero is a special case. 0! is defined as 1.

  9. Nosredna said,

    April 14, 2010 at 1:58 am

    OK. I just fixed combinations, hopefully. I expect you’ll tell me next that permutations has a similar problem?

  10. James Heo said,

    May 23, 2011 at 7:37 am

    var n=parseInt(prompt(“n!, input interger”,”100″));

    if(isNaN(n)==true){alert(‘Please, input interger’);}

    var big_integer=Math.pow(2,52.5);

    var R_TXT=[];var cnt=0; var factorial_past=0;

    function F(m,n) {

    var factorial=m;var multiply=1;

    var multi_past;

    while(factorialbig_integer){R_TXT[cnt++]=(factorial-1)+”!/”+factorial_past+”! = “+(factorial_past+1)+” ~ “+(factorial-1)+” = “+multi_past;
    factorial_past=(factorial-1);return F(factorial,n);}

    factorial++;}

    return multiply;}

    var N=F(1,n);

    R_TXT[cnt++]=n+”!/”+factorial_past+”! = “+(factorial_past+1)+” ~ “+n+” = “+N;

    document.write(n+’ Factorial ‘+(R_TXT.length-1)+” Numbers”+(R_TXT).join(”));

  11. James Heo said,

    May 23, 2011 at 7:43 am

    Oh, No…
    “” where is this? Do not erase~!

    • James Heo said,

      May 23, 2011 at 7:45 am

      ~than big sign, ~than small sign ..
      do not erase~!

  12. Davis said,

    January 20, 2012 at 3:04 pm

    Unfortunately this formula is still not correct when there is a zero involved.. Using combinations(2,0) it returns 3. It should return 1.
    eg. n=2, k=0
    then in the function k is set to max(0,2-0) = 2
    then calling productRange(2+1,2) = 3 / productRange(1,0) = 1
    = 3


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: