Results 1 to 13 of 13
Thread: Combinations in Java
 08252011, 03:43 PM #1Member
 Join Date
 Jul 2011
 Posts
 3
 Rep Power
 0
Combinations in Java
I'm very new to Java, I want to write a very simple program to find the number of ways, n, of selecting several things out of a given group which has 5 elements. The formula for this combination is 5!/n!(5n)! with n<=5. I started out with
public int combinations (int number){
The input to the method must be an integer, and the method must also return an integer. How can I define the factorials in the denominator "n!" and "(5n)!" in Java? For the numerator it's just 5!=5*4*3*2, but in the denominator it all depends on what value from the interval 05 the user chooses...
I'd greatly appreciate it if anyone could show me a simple way of doing this.
 08252011, 03:55 PM #2
How would you do this by hand, with a piece of paper and a pencil? Pretend you have a friend who has no idea how to do this. Write a stepbystep guide that he could follow to get the correct answer. When you have that, you'll have an algorithm that should be pretty easy to translate to code.
How to Ask Questions the Smart Way
Static Void Games  Play indie games, learn from game tutorials and source code, upload your own games!
 08252011, 04:08 PM #3
with a combination, order does not matter, versus a permutation where order does. So if I understand what you are trying to do, you actually need 2 inputs, 'n choose r', where n is the sample space and r is how many you are picking.
Last edited by sehudson; 08252011 at 04:19 PM.
 08252011, 04:12 PM #4
Hooray spoonfeeding! Why teach a man to fish when you can just give him one and be on your way?
Edit Spoonfeeding removed, nevermind.Last edited by KevinWorkman; 08252011 at 06:13 PM.
How to Ask Questions the Smart Way
Static Void Games  Play indie games, learn from game tutorials and source code, upload your own games!
 08252011, 05:26 PM #5Member
 Join Date
 Aug 2011
 Posts
 95
 Rep Power
 0
I see that 'factorial' (the mathematical "!" operator) appears three times in your formula. And figuring out how to compute a factorial is a nifty little trick. So I would probably also define a second function:
Java Code:public int factorial(int number) { ... }
After you implement this function, making the "combinations" function work will be a lot easier.
 08252011, 05:32 PM #6Member
 Join Date
 Aug 2011
 Posts
 95
 Rep Power
 0
I agree with sehudson, in that I would probably implement a combinations function that solves the general problem of 'n' things taken 'k' at a time:
Java Code:public int combinations(int n, int k) { ... }
But that's more general than the question you asked.
I would first get the function you wrote working correctly. And then I would consider generalizing it.
 08252011, 06:11 PM #7
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
With some simple searching on this forum you can find a recursive factorial function(hint: Check the blogs).
 08252011, 08:08 PM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,783
 Blog Entries
 7
 Rep Power
 21
It would be extremely silly to calculate C(n,k) with a factorial function (whether recursive or not). Even 13! can't be calculated using ints. We can do better than that. e.g. if we want to calculate C(13,4) we have two options: 13*12*11*10*9*8*7*6 *5/9*8*7*6*5*4*3*2*1 or 13*12*11*10/4*3*3*1 (check this ;)
Obviously we should do the second, i.e. we take m= min(nk,k) which determines the denominator; the numerator has m terms up to n. We can do the divisions on the fly because it we multiply r consecutive numbers we know that the product can be evenly divided by r. So a single loop could do it:
Java Code:int m= min(nk, k); int cnm= 1; for (int i= nm+1, j= 1; i <= n; i++, j++) { cnm*= i; cnm/= j; } return cnm;
JosLast edited by JosAH; 08252011 at 08:22 PM.
cenosillicaphobia: the fear for an empty beer glass
 08252011, 09:09 PM #9Member
 Join Date
 Aug 2011
 Posts
 95
 Rep Power
 0
One could use 'long', 'double' or 'BigInteger' to deal with big numbers.
And let's see what happens when his instructor asks him to explain that short and efficient version.
 08252011, 09:50 PM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,783
 Blog Entries
 7
 Rep Power
 21
cenosillicaphobia: the fear for an empty beer glass
 08252011, 09:53 PM #11Member
 Join Date
 Aug 2011
 Posts
 95
 Rep Power
 0
To heck with it; I'll use smalltalk.
 08252011, 10:19 PM #12
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,783
 Blog Entries
 7
 Rep Power
 21
 08252011, 11:22 PM #13Member
 Join Date
 Jul 2011
 Posts
 3
 Rep Power
 0
Similar Threads

Possible combinations for a n digit number???
By anishr6 in forum New To JavaReplies: 4Last Post: 05252011, 09:55 AM 
All possible combinations given a binary number
By LeanA in forum New To JavaReplies: 9Last Post: 06182010, 06:33 PM
Bookmarks