Counting Permutations in C/C++: Dealing with Large Factorials

The following is a coding interview question. Suppose you’re given 10 positions, 1 item of kind A and 9 items of kind B. How many different ways are there to arrange these items in 10 positions? Standard formula says 10! / (9! 1!) so the answer is 10. Using a more general version, it says n! / (a! b! c! d!). All is swell when the numbers are relatively small since you can compute their factorials using some primitive implementation, then multiply the numbers out for denominator and perform division. But when the numbers get just a bit bigger, their factorials become very large, you can’t use brute-force approach – you’ll have to come up with a smarter schema.

There is a lot of cancellation going on here. 10! expands to 10 . 9 . 8. 7 . 6 … while 9! in denominator becomes 9 . 8 . 7 . 6 … and the whole thing just cancels out! Is there a way to capitalize on this symmetry? You bet…

Let’s have an integer array a of size n. In the beginning, we make every element of a -1. Then we start iterating over numbers in the denominator. For every number b, will scan  a from 1 to b and increment. When we do it for all integers in the denominator, we’re ready to take factorials. If a[i] is -1, then i goes to numerator and a[i] > 0 means that i goes to denominator. Also, if a[i] > 1 means that denominator has to be multiplied by i a[i] many times. This doesn’t apply to numerator since -1 is the minimal it can go.

What happens if one of the bottom numbers is greater than n? Well, technically it shouldn’t since we presume that we’re trying to compute number of permutations and the count of objects of any one type cannnot exceed available number of positions. In fact, sum of numbers in a should be n so that every position is supposed to have an object of some type and no item should be left out.

Here is my version of the code:
unsigned long long factorialLong(int numerator, int n, int * a){
int nn = numerator + 1;
      int * num = (int * ) malloc (sizeof(int) * nn);
      if (num == NULL)
           return(-1);
      int i;
      int j;
      for (i = 0; i < nn; i++) {
            num[i] = -1;
      }
      for (i = 0; i < n; i++){
            for (j = 1; j <= a[i]; j++){
                  num[j]++;
            }
      }
      unsigned long long np = 1;
      unsigned long long dp = 1;
      for (i = 1; i < nn; i++) {
            if (num[i]==-1) {
                  np *= i;
            }
            if (num[i]>0){
                  for (j = 1; j <= num[i]; j++) dp *= i;
            }
      }
      free(num);
      return( np / dp);
}

Advertisements

~ by Monsi.Terdex on June 7, 2013.

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

 
Normal Boy

Nothing out of the ordinary

Data Engineering Blog

Compare different philosophies, approaches and tools for Analytics.

%d bloggers like this: