CODEWITHSUNDEEP
c#algorithmcombinationsfactorial
Abdul
Abdul

Reputation: 458

Unable to calculate number of combinations due to very large factorial

I am trying to calculate the number of combinations of the number of elements in a certain array. I need the exact number of combinations to use it as number of threads to be executed in the GPU.

But the data is very big and the factorial can't be calculated for that big a number with any data type.

Is there a way to calculate the number of combinations without having to find the factorial? Or a more efficient way to do so?

It summarizes the problem:

int no_of_combinations = combination(500,2);
public static int factorial(int m)
{
        int x = 1;

        for (int i = m; i > 0; i--)
            x = x * i;

        return x;
}
public static int combination(int m, int n)
{
    int x = 0;
    x = factorial(m) / (factorial(n) * factorial(m - n));
    return x;
}

Upvotes: 1

Views: 1151

Answers (4)

Douglas Zare
Douglas Zare

Reputation: 3316

You don't need to use factorials. If k>n/2, then use C(n,k)=C(n,n-k). Then use that C(n,0)=1 and for k>0, C(n,k) = C(n,k-1) * (n-k+1)/k. This lets you compute almost as many binomial coefficients as the dynamic programming method but it takes linear time (Theta(min(n-k,k))) and constant space instead of quadratic time and linear space.

See this past question: How to efficiently calculate a row in pascal's triangle?

public static long combination(int n, int k)
{
  if (n-k < k)
    return combination(n,n-k);
  if (k < 0)
    return 0;
  long result = 1;
  for (int i=1; i<=k; i++)
  {
    result *= n-i+1;
    result /=i;
  } 
  return result;
}

This may overflow if the answer times n exceeds the maximum long. So, if you expect the answer to fit in a 32 bit int and you have 64 bit longs, then this should not overflow. To avoid overflowing, use BigIntegers instead of longs.

Upvotes: 2

Owen Ivory
Owen Ivory

Reputation: 244

You need to write a new function, lets call it FactorialMoverN

int FactorialMOverN(int m, int n)
{
    int x = 1;
        for (int i = m; i > n; i--)
            x = x * i;
    return x;
}

Then change your combination function to

x = FactorialMOverN(m,n) * factorial(m - n));

This should help. If it doesn't help, then you need to use a different variable type, or rethink your problem.

Thanks to Sami, I can see that the above function is in error. The 500 choose 2 needs to be calculated via

int MChooseN(int m, int n)
    {
        int x = 1;
            for (int i = m; i > (m-n); i--)
                x = x * i;
        return x;
    }

The above will take 500, 2 and return 500*499, the previous would have taken 500,2 and returned 500*499*498...5*4*3 which is not what you wanted.

Anyway, the above is the best you can get.

Upvotes: 0

Sami Kuhmonen
Sami Kuhmonen

Reputation: 31143

In this case I would start to simplify the equation. In your example you're looking for 500 choose 2, which is 500!/498!/2!. This can be easily changed to 500*499/2, which can be calculated.

In general terms if you have n choose k, you only need to calculate a "partial factorial" from n to max(k, n-k) and then divide by min(k, n-k)! due to the results being mirrored. This makes the calculation much easier.

Also in certain cases you could start dividing with the min(k, n-k)! while multiplying, but that will lead to remainders etc.

Upvotes: 4

Boris Strandjev
Boris Strandjev

Reputation: 46943

Use the Pascal's triangle property:

C(n,k) = C(n - 1, k) + C(n - 1, k - 1) and dynamic programming. No factorials involved.

The triangle of Pascal being:

        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1

Upvotes: 3

Related Questions