CODEWITHSUNDEEP
javarecursioncombinations
adammenges
adammenges

Reputation: 8818

Recursion to get the number of different combinations of n people and k groups

I'm practicing recursion using Java and I've hit a problem. I'm trying to make a method which I'm calling "groups" which takes a number of people and how many groups there are and returns the number of different combinations there are of people and groups. Also, the ordering of people in the groups does not matter, nor does the ordering of the groups.

The code I have so far is:

public long groups(int n, int k) {
    if(k==1) return 1;
    if(k==n) return 1;
    else return groups(n-1, k) + groups(n-1, k-1);
}

However it returns the wrong values. The first two lines are the base cases, which say if there is 1 group, then there is only one way to split the people up, makes sense. The other is when there are just as many people as there are groups, in which case theres only one way to split them up, one person into each group. The last statement is where I think I'm having problems, I would think that each time it does a recursive call, one person has to be taken out (n is the number of people, so n-1) and that person can ether join a group (k) or make their own group (k-1).

I'm just having a little trouble figuring out how recursion works and could use a little help.

These are the values I'm expecting:

groups(2,1) = 1
groups(2,2) = 1
groups(3,2) = 3
groups(4,2) = 7
groups(4,3) = 6
groups(5,3) = 25

Upvotes: 4

Views: 1691

Answers (2)

user85421
user85421

Reputation: 29680

There is something missing in the implementation of that part

... and that person can ether join a group (k) ...

I think the person can join 'k' groups, so the code must be 

    public long groups(int n, int k) {
        if(k==1) return 1;
        if(k==n) return 1;
        else return k * groups(n-1, k) + groups(n-1, k-1);
    }

(was missing multiplication by k)

Upvotes: 4

Ken Bloom
Ken Bloom

Reputation: 58770

There's a much easier (faster) way to compute combinations -- that's the binomial coefficient. While I can understand that your teacher may want you write a recursive function this way to become familiar with recursion, you can use this formula as a check.

In your case, you're reporting the wrong expected values here. What you want is 

groups(2,1) = 2
groups(2,2) = 1
groups(3,2) = 3
groups(4,2) = 6
groups(4,3) = 4
groups(5,3) = 10

and the code you've posted is correct if the values above are what it's supposed to return.

(If not, perhaps you can better clarify the problem by explaining more clearly how the problem you're solving differs from the binomial coefficient.)

Upvotes: 0

Related Questions