Number of combinations

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?

-
If you question is about how to handle large numbers in C, and not about factorials or recursion then you should change the question. – WuHoUnited Feb 14 '12 at 5:38
Why do you want to avoid recursion? – SRKX Feb 14 '12 at 8:38
@SRKX There are good reasons to avoid recursion, it almost always introduces overhead (the exception being tail-recursion) and in some scenarios stack-overflow. Also, when computing factorial there is not even a benefit to it. – Bernd Elkemann Feb 14 '12 at 14:28
@eznme : I know. I was trying to see what his motivations were. – SRKX Feb 14 '12 at 14:31
@SRKX understood – Bernd Elkemann Feb 14 '12 at 16:19

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:

`100! = 9.33262154 × 10^157`

using Stirling's Approximation:

`100! = 9.3224838328837612788449900430478 x 10^157`

That's close enough for me :)

-
Your suggestion is good. The expected error is 1/12n of n! according to page 590 in books.google.ca/… – NoChance Feb 14 '12 at 8:33

What is wrong with using the formula:

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

You don't need recursion to calculate a factorial.

-
but how to work with number such as 100!? – Jay Feb 14 '12 at 5:24
Then you need to use a library that supports a big integer, but you can still use the same formula. – WuHoUnited Feb 14 '12 at 5:27
Or, if an an approximate answer is ok, you can use the gamma function. For historical reasons in the 'C' runtime this function is called tgamma (think 'true gamma'). tgamma(n) ~ (n-1)!, but the argument and return values are doubles, so you can accommodate quite large number. – Charles E. Grant Feb 14 '12 at 5:38

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.

-

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)!

-

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: