Recursion - Java Concepts - page 848

΢΢΢ Exercise P13.9. Implement a SubstringGenerator that generates
all substrings of a string. For example, the substrings of the string
"rum" are the seven strings

"r", "ru", "rum", "u", "um", "m", ""

Hint: First enumerate all substrings that start with the first character.
There are n of them if the string has length n. Then enumerate the
substrings of the string that you obtain by removing the first character.

΢΢΢ Exercise P13.10. Implement a SubsetGenerator that generates all
subsets of the characters of a string. For example, the subsets of the
characters of the string "rum" are the eight strings

"rum", "ru", "rm", "r", "um", "u", "m", ""

Note that the subsets don't have to be substringsȌfor example, "rm"
isn't a substring of "rum" .

΢΢΢ Exercise P13.11. In this exercise, you will change the
PermutationGenerator of Section 13.2 (which computed all
permutations at once) to a PermutationIterator (which computes
them one at a time.)

public class PermutationIterator
{
public PermutationIterator(String s) { È }
public String nextPermutation() { È }
public boolean hasMorePermutations() { È }
}

Here is how you would print out all permutations of the string "eat" :

PermutationIterator iter = new
PermutationIterator("eat");
while (iter.hasMorePermutations())
System.out.println(iter.nextPermutation());

620
621

Now we need a way to iterate through the permutations recursively.
Consider the string "eat" . As before, we'll generate all permutations
that start with the letter ÓeÓ , then those that start with ÓaÓ , and finally
those that start with ÓtÓ . How do we generate the permutations that start