| CIS 210 Home Page | Last updated 2007/11/01 14:10:23 |
In problem 4.1, you calculated the number of ways to choose M items from a collection of N items. In that assignment, the focus was on using BigInteger objects for the calculation and you saw that primitive Java int's could not handle the large numbers from the factorial calculation in the formula.
We will revisit the calcuation of choices in this problem, but use recursion to see if we can get Java int's to work for some more values. Because recursion can be inefficient, this is still not as good of a solution as the BigInteger's, but it is easier to code.
To see how we can use recursion for the choices problem, let's first think about base cases. Rememberg that in this problem there are two numbers to consider: N, the total number of items from which we can choose, and M, the number of items to choose.
If the number of items to choose is just one, then how many ways can we do that? Well, if there are N items total, we can clearly choose any one of those, so that means N different ways to choose the one item. This could be a base case.
Another situation to consider is if the number of items to choose is the same as the total number of items. Clearly, there is only one way to make this choice - we have to choose all of the items. This could be another base case.
We need to see how to decompose the problem recursively. That is, we want to break the choices of N things M at a time into smaller problems. If we had one less item, how would that help? One way to view this problem is to consider what happens if we set one of the total items aside. Then we would have N-1 items. If we choose M of these items, we do have a choice of M items (they just don't include the set aside item). The calculation of this count is a smaller problem, so that sounds like recursion, and indeed this is at least part of the answer we're seeking. But it doesn't account for all of the possible choices of M items from the original N. In particular, the choices that involved the set aside item are not counted. So, how many of these choices are there? If we have the set aside item, then we need to have M-1 more items from the remaining N-1 items. Again, a smaller problem and the other part that we need.
If you think about this, you'll see that we have counted all the possible choices of N items taken M at a time by breaking the count into two smaller problems. When we add the solutions of the two smaller problems, we get the answer we're looking for. A Java implementation of this recursion will only involve addition, so we won't get the large numbers that quickly overflowed in the factorial calculation. However, because the recursion splits into two with each reduction. we do have an exponential explosion in the number of recursive calls, and this will cause the program to take a huge amount of time for large values, much like the Fibonacci problem.
The main code in RecursiveChoices.java will help you get started. You can enter values on the command line or be prompted for them.
You should run your solution (or the model solution) from problem 4.1 and compare the results. If you choose large values for N or M, the program may slow down so much that you never see an answer and have to kill the process. But you should at least be able to run the examples shown and similar values.The number of ways to choose 5 things from 10 is: 252 The number of ways to choose 5 things from 20 is: 15504 The number of ways to choose 5 things from 30 is: 142506 The number of ways to choose 5 things from 40 is: 658008 The number of ways to choose 12 things from 30 is: 86493225