1

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;
}
Abdul
  • 458
  • 5
  • 20
  • Can you be more specific? Which formula and what is "very big" ? Btw, there is a dedicated site for all math-related questions: [http://math.stackexchange.com/](http://math.stackexchange.com/). – Sinatr Dec 09 '15 at 15:39
  • 1
    I am not sure if this is going to help but have you looked up Stirling's approximation? It is an approximation of factorials. – Alchemist Dec 09 '15 at 15:40
  • 5
    if you cant even represent the number with a known data type, how are you going to make the same amount of threads? – HansP Dec 09 '15 at 15:41
  • 1
    @HansP, he is using factorial in formula. Number of threads (result of formula) might be ok (reasonable). – Sinatr Dec 09 '15 at 15:42
  • 3
    I'd recommend simplifying the equation beforehand, instead of trying to evaluate 500!, see if you can simplify the fraction – Ryan Fitzpatrick Dec 09 '15 at 15:46
  • @Sinatr typically, the number of elements is in hundreds. as things are right now, i can't calculate the factorial of even "100". – Abdul Dec 09 '15 at 15:46
  • 1
    From comment your question is more like duplicate of [Calculate factorials in C#](http://stackoverflow.com/questions/4186357/calculate-factorials-in-c-sharp) – Sinatr Dec 09 '15 at 15:49
  • 1
    @RyanFitzpatrick YOU ARE A GENIUS!!!! thanks a lot :) – Abdul Dec 09 '15 at 15:49
  • @AbdulRehman Glad I could help :) – Ryan Fitzpatrick Dec 09 '15 at 15:52

4 Answers4

4

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.

Sami Kuhmonen
  • 30,146
  • 9
  • 61
  • 74
  • Actually this is also a valid approach, better to go with the prime divisors though, using Lagendre's formula: https://en.wikipedia.org/wiki/Legendre%27s_formula – Boris Strandjev Dec 09 '15 at 16:13
  • @BorisStrandjev: In what sense is that better? What's the running time, for example? – Douglas Zare Dec 12 '15 at 01:54
  • @DouglasZare you can afford calculating a lot huger numbers in the approach I propose without fearing overflow. The runnign time for a single combination will be slower, as you need the eratosthenes sieve precalculation, but for multiple calculations it will be faster. – Boris Strandjev Dec 12 '15 at 09:26
  • What is the running time, and how much space does it take? To say it is better than the approach I gave, you should at least match running time that is linear in min(n-k,k) or constant space. It looks to me like it is both slower (in practice and theory) and takes more space, even if you allow a lot of precomputation. Here is an implementation in Lolcode: http://thenerdiestshirts.ecrater.com/p/12755673/programming-t-shirt-size-l-unisex-white. How much code does it take to use Legendre's formula, and what is the chance someone asking the original question will implement it correctly? – Douglas Zare Dec 12 '15 at 15:20
3

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
Boris Strandjev
  • 46,145
  • 15
  • 108
  • 135
2

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.

Community
  • 1
  • 1
Douglas Zare
  • 3,296
  • 1
  • 14
  • 21
0

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.

Owen Ivory
  • 244
  • 1
  • 9