programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# N choose K Recursion Question?

Ranch Hand
Posts: 32
I recently wrote a simple recursive program that chooses K objects out of N (I was asked to use the variables N choose the R, however) total objects.
Here is the code:

It works fine, however in my class we were given two different formula to implement into our code. I used the one above, obviously. However, the second formula we were given was:

C(n,R) = n!
-------(R!(n-R)!)

Sorry for the ----- but I had to get the spacing right.

I'll be honest, I don't really understand how to read this formula. I am curious, however. How do I read this formula? How could it be implemented? What are the benefits (if there are any) from using one method over the other? Which method of calculating N choose K (or, in my case, N choose R) would be more widely accepted, in your opinion?
Thank you for any help!

Bartender
Posts: 689
17
• 1
When you say you don't know how to reqd the formula, I will assume it is the '!' that is confusing you. This is known in maths as the factorial, and is a shorthand for the following:

n! = n * (n -1) * (n - 2) * ... * 2 * 1

So 5! = 5 * 4 * 3 * 2 * 1 = 120.

A Axford
Ranch Hand
Posts: 32
Ah, okay. So, correct me if I have this wrong, but the equation would be like saying:

the number of total objects (lets say 6 objects) * n -6 * n- 5 * n - 4 * n - 3 * n- 2 * n - 1 / the number of chosen objects (lets say 2) * R - 2 * R -1 * (number of total objects - number of chosen objects) * R -2 * R-1

Not sure if I have the general logic right or not...?

Marshal
Posts: 59080
180
• 1
Not quite. You can read about permutations on Wikipedia; I haven't found their combinations page but I am sure it will be there.
The formula for nCr, whch is what it was called when I was at School (we still had steam trains on main lines in those days ‍) is n! ÷ ((n − r)! × r!). For ₆C₄ that comes to 6 × 5 × 4 × 3 × 2[ × 1] ÷ ((4 × 3 × 2[ × 1]) × (2[ × 1])), which reduces to 15.
That means there are 15 different ways to draw 4 our of 6, as long as you don't care about the order of drawing: 1234 1235 1236 1245 1246 1256 1345 1346 1356 1456 2345 2346 2356 2456 3456, and there are also fifteen ways to draw two out of six which are the same as the ways of leaving two behind (i.e. the complement of the above fifteen sets): 56 46 45 36 35 34 26 25 24 23 16 15 14 13 12.

A Axford
Ranch Hand
Posts: 32
Thank you very much for explaining. I was able to figure out how to code it both ways.

I'll mark this as resolved.

 That which doesn't kill us makes us stronger. I think a piece of pie wouldn't kill me. Tiny ad: Rocket Oven Kickstarter - from the trailboss https://coderanch.com/t/695773/Rocket-Oven-Kickstarter-trailboss