1. Member
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!(5-n)! 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 "(5-n)!" 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 0-5 the user chooses...

I'd greatly appreciate it if anyone could show me a simple way of doing this.

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 step-by-step 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.

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; 08-25-2011 at 04:19 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; 08-25-2011 at 06:13 PM.

5. Member
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) { ... }`
So that if I pass it 5, it will return 120. And other appropriate results, as one would expect.

After you implement this function, making the "combinations" function work will be a lot easier.

6. Member
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) { ... }`
as defined here: Wikipedia: Combination

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.

7. With some simple searching on this forum you can find a recursive factorial function(hint: Check the blogs).

8. Originally Posted by sunde887
With some simple searching on this forum you can find a recursive factorial function(hint: Check the blogs).
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(n-k,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(n-k, k);
int cnm= 1;

for (int i= n-m+1, j= 1; i <= n; i++, j++) {
cnm*= i;
cnm/= j;
}

return cnm;```
kind regards,

Jos
Last edited by JosAH; 08-25-2011 at 08:22 PM.

9. Member
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.

10. Originally Posted by JeffGrigg
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.
Using longs doesn't buy you much, 21! doesn't fit in a signed long. Doubles are even worse if you want an exact answer (53 bits of mantissa). BigInteger can be a solution but it also is overkill as long as they aren't needed ;-)

kind regards,

Jos

11. Member
Join Date
Aug 2011
Posts
95
Rep Power
0
To heck with it; I'll use smalltalk.

12. Originally Posted by JeffGrigg
To heck with it; I'll use smalltalk.
That's cheating; SmallTalk uses those big monsters too behind our backs ;-)

kind regards,

Jos

13. Member
Join Date
Jul 2011
Posts
3
Rep Power
0
Oops. I got it. Thanks a lot JosAh!
Last edited by Roam; 08-25-2011 at 11:32 PM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•