Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
2  
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. –  eznme 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 –  eznme Feb 14 '12 at 16:19

5 Answers 5

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

Stirling's Approximation

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

share|improve this answer
    
Your suggestion is good. The expected error is 1/12n of n! according to page 590 in books.google.ca/… –  Emmad Kareem 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.

share|improve this answer
1  
but how to work with number such as 100!? –  Jay Feb 14 '12 at 5:24
2  
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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.