Number of combinations

Question

How to go about getting the number of combination ( C(5,4) ) without using recursion in C? Is there any other method or inbuilt library to do this?

Answer 1

You can avoid recursion and looping completely if an approximation is acceptable, you can use Stirling's Formula to approximate the answer.

Example

Option 1: Recursively or iteratively calculate factorial(n)

5! = 5x4x3x2 = 120

Option 2: Use Stirling's Approximation

5! ~ sqrt(2*pi*5) * (n/e)^n = sqrt(10*pi) * (5/2.718281828)^5 
                            = sqrt(31.41592654) *  (1.839397206)^5
                            = 5.604991216 * 21.05608437
                            = 118.019168 (close to 120) 

(Note: ~ means approximately and e is Euler's number defined 2.718281828)

This may seem silly because 5! is so small, but for a number like 100! the approximation works fairly well.

Large example, n = 100:

according to Google :

100! = 9.33262154 × 10^157

using Stirling's Approximation:

100! = 9.3224838328837612788449900430478 x 10^157

That's close enough for me :)

Answer 2

What is wrong with using the formula:

n!/(k! (n-k)!).

You don't need recursion to calculate a factorial.

Answer 3

Optimize the combination formula. If \binom{n}{r} is asked, first set r to be (r) or (n-r), whichever is smaller. Now use the normal shortcut method for finding combinations without calculating full factorials:

(n)(n-1)....(n-r+1)[r terms]/r!

Use Stirling's formula if the numbers are too large. You don't have to use recursion, for loops are more efficient (though less aesthetically pleasing) for factorials and continued products.

Answer 4

To calculate factorial for large numbers you can use a biginteger-library or arbitrary-precision library like http://gmplib.org/ or do it yourself (arbitrary-precision multiplication is easy, division not so) by using an array of unsigned ints.

Since you dont want to do it recursively, just iterate through the numbers from 1 to n, multiplying each of them into an biginteger you initialize with 1.

Then to calculate the number of combinations not permutations you calculate n!/k!/(n-k)!

Answer 5

I assume you can construct a simple function to calculate n! = nx(n-1)x(n-2)x...x1. Now for large numbers, you may need to divide your algorithm as follows:

part1: when the input number has an acceptable value to be used with the formula above. I am not a C developer, so I can't tell you what is this value, for now we'll call it (L). For this case, you simply apply the above formula.

part2: When the input number is greater than the acceptable value L:The formula c(n,k) = nx(n-1)x(n-2)x....x(n-k)!/((n-k)!*k!) this can be simplified as:

c(n,k)=nx(n-1)x(n-2)x....x(n-k+1)/k! (see Related Answer)

this last equation involves smaller values than those in the original expression.

if k! in the above expression is less than or equal to L, then use the regular formula.

if k! > L or if nx(n-)x...x(n-k+1) > L you can use Sterling's formula as suggested by @Hunter McMillen