• Post Reply Bookmark Topic Watch Topic
  • New Topic
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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

N choose K Recursion Question?

 
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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!

 
Bartender
Posts: 689
17
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
A Axford
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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...?
 
Marshal
Posts: 79177
377
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
A Axford
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
reply
    Bookmark Topic Watch Topic
  • New Topic