• Post Reply Bookmark Topic Watch Topic
  • New Topic

N choose K Recursion Question?  RSS feed

 
Aarden Axford
Greenhorn
Posts: 28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!

 
Mike. J. Thompson
Bartender
Posts: 689
17
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Aarden Axford
Greenhorn
Posts: 28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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...?
 
Campbell Ritchie
Marshal
Posts: 56593
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Aarden Axford
Greenhorn
Posts: 28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you very much for explaining. I was able to figure out how to code it both ways.

I'll mark this as resolved.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!