Thinking Recursively with Java

6.1. Exercises

6-1.	Using the index-card method described in Chapter 5, go through the operation of the listPermutations method for the string "ABCD".
6-2.	Using mathematical induction, prove the following proposition: If the characters in str are in alphabetical order (as they are, for example, in the string "ABCD"), then listPermutations(str) will always generate the permutations in alphabetical order.
6-3.	In this chapter (and in the earlier discussion in Chapter 3), the characters in the string were assumed to be distinct. If they are not, the code for listPermutations developed in this chapter will generate repeated entries. For example, if you call listPermutations("ABBC"), every entry will appear twice. Think about how you could improve the implementation so that the list includes no duplicate entries. Figure 6-1. Code to test the listPermutations procedure
6-4.	Like the problem of generating permutations, the problem of generating all subsets of a set of N elements has a simple recursive formulation. For example, if you start with the set {A, B, C}, the set of all subsets can be divided into two groups: (1) those that contain A and (2) those that do not. In either case, the subsets in each group simply contain all possible subsets of the remaining elements {B, C}. Thus, the complete list of subsets of {A, B, C} is Using a string of characters to represent a set, write a ...