CODEWITHSUNDEEP
java
gruevy
gruevy

Reputation: 3

Recursive Permutation (counting rule)

I looked through a bunch of questions and I didn't find this. I need to write a recursive method that returns a Permutation, P(N,K). Meaning, pool of 20 objects, draw 3, how many possibilities are there for the order you draw them in? The answer is 20*19*18.

Here's what I've got so far:

public double perm(long N, long K)

{
   if (K == 1)
      return N;
   else
      return perm((N*(N-1)), (K-1));
}

N is the pool, K is how many pulls. My problem is figuring out how to make the "N*(N-1)*(N-2)..." bit work. Say I do this:

perm(10,3)

After my first time through the code I've got, N would be 10*9, or 90, which means that on the second loop, it'd be calculating 90*89, not (10*9)*8. I can't figure out how this is supposed to work, but the professor assigned it so it must be possible.

I could do this really easily with a FOR lop, but it can't be a for loop. I don't really want the solution, just some guidance. Thanks!

Upvotes: 0

Views: 51

Answers (1)

alegria
alegria

Reputation: 1145

You're recursing (is that a word?) with the multiplication result.

return perm((N*(N-1)), (K-1));

Here, N*(N-1) = 90 (N being 10 initially), hence the result perm(90), k-1)

You should multiply the result of P(N-1, K-1) with N like :

N * P(N-1, K-1)

Upvotes: 1

Related Questions