# Combinations in Java

• 08-25-2011, 03:43 PM
Roam
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. :)-:
• 08-25-2011, 03:55 PM
KevinWorkman
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.
• 08-25-2011, 04:08 PM
sehudson
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.
• 08-25-2011, 04:12 PM
KevinWorkman
Hooray spoonfeeding! Why teach a man to fish when you can just give him one and be on your way?

Edit- Spoonfeeding removed, nevermind.
• 08-25-2011, 05:26 PM
JeffGrigg
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:
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. :o:
• 08-25-2011, 05:32 PM
JeffGrigg
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:
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.
• 08-25-2011, 06:11 PM
sunde887
With some simple searching on this forum you can find a recursive factorial function(hint: Check the blogs).
• 08-25-2011, 08:08 PM
JosAH
Quote:

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:

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
• 08-25-2011, 09:09 PM
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. :)-:
• 08-25-2011, 09:50 PM
JosAH
Quote:

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
• 08-25-2011, 09:53 PM
JeffGrigg
To heck with it; I'll use smalltalk. :D:
• 08-25-2011, 10:19 PM
JosAH
Quote:

Originally Posted by JeffGrigg
To heck with it; I'll use smalltalk. :D:

That's cheating; SmallTalk uses those big monsters too behind our backs ;-)

kind regards,

Jos
• 08-25-2011, 11:22 PM
Roam
Oops. I got it. Thanks a lot JosAh!