Results 1 to 13 of 13
Like Tree3Likes
  • 1 Post By KevinWorkman
  • 1 Post By JosAH
  • 1 Post By JosAH

Thread: Combinations in Java

  1. #1
    Roam is offline Member
    Join Date
    Jul 2011
    Posts
    3
    Rep Power
    0

    Default 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. #2
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,965
    Rep Power
    8

    Default

    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.
    JeffGrigg likes this.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    sehudson's Avatar
    sehudson is offline Senior Member
    Join Date
    Mar 2010
    Posts
    356
    Rep Power
    5

    Default

    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 03:19 PM.

  4. #4
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,965
    Rep Power
    8

    Default

    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 05: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!

  5. #5
    JeffGrigg is offline Member
    Join Date
    Aug 2011
    Posts
    95
    Rep Power
    0

    Default

    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. #6
    JeffGrigg is offline Member
    Join Date
    Aug 2011
    Posts
    95
    Rep Power
    0

    Default

    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. #7
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

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

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,541
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by sunde887 View Post
    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 07:22 PM.
    Roam likes this.
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    JeffGrigg is offline Member
    Join Date
    Aug 2011
    Posts
    95
    Rep Power
    0

    Default

    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. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,541
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by JeffGrigg View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  11. #11
    JeffGrigg is offline Member
    Join Date
    Aug 2011
    Posts
    95
    Rep Power
    0

    Default

    To heck with it; I'll use smalltalk.

  12. #12
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,541
    Blog Entries
    7
    Rep Power
    20

    Default

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

    kind regards,

    Jos
    JeffGrigg likes this.
    cenosillicaphobia: the fear for an empty beer glass

  13. #13
    Roam is offline Member
    Join Date
    Jul 2011
    Posts
    3
    Rep Power
    0

    Default

    Oops. I got it. Thanks a lot JosAh!
    Last edited by Roam; 08-25-2011 at 10:32 PM.

Similar Threads

  1. Possible combinations for a n- digit number???
    By anishr6 in forum New To Java
    Replies: 4
    Last Post: 05-25-2011, 08:55 AM
  2. All possible combinations given a binary number
    By LeanA in forum New To Java
    Replies: 9
    Last Post: 06-18-2010, 05:33 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
  •