Permuting String in Java. Explain please?

Question

I've been working through an example in a book that shows you how to permute a String into all it's possible combinations, but as I'm still quite a beginner at programming in general, I can't actually understand how the code works!

Could someone please analyze the code I've supplied and give me a thorough explanation of what everything does and how it does it?

Many thanks,

Alex.

class PermuteString{
    String word;
    int index;
    PermuteString substringGenerator;
    public PermuteString(String s){
        word = s;
        index = 0;
        if(s.length() > 1){
              substringGenerator = new PermuteString(s.substring(1));
    }
}

public String nextPermutation(){
    if(word.length() == 1){
        ++index;
        return word;
    }
    else{
        String r = word.charAt(index) + substringGenerator.nextPermutation();
        if(!substringGenerator.morePermutations()){
            ++index;
            if(index < word.length()){
                String tailString = word.substring(0, index) + word.substring(index + 1);
                substringGenerator = new PermuteString(tailString);
            }
        }
        return r;
    }
}

public boolean morePermutations(){
    return index < word.length();
}

}

public class PermuteStringDemo {
public static void main(String[] args){
    PermuteString p = new PermuteString("opyn");
    while(p.morePermutations())
        System.out.println(p.nextPermutation());
}
}

Nick Straguzzi · Accepted Answer

Keep in mind that this is not the clearest or the easiest way to permute a string. In fact, in terms of programming style, it's unspeakably wretched. Rather it's a textbook example to illustrate a form of recursion. The easiest way to understand what's going on is to take things step by step.

Start with the constructor. It saves the word, sets its index to 0, and then (if necessary) creates a new PermuteString object from the 2nd through last character of the word. When this is done, you have what amounts to a linked list of PermuteString objects: first for "opyn", then "pyn", "yn", "n" in that order. Easy enough.

Now let's look at the iterator. morePermutations() serves as the equivalent of next() in a standard Iterator; it returns true if its index is still less than the length of its word. So, you know that when a PermuteString index reaches the length of its word, it's done.

Finally, nextPermutation().

For one-letter words, it returns its word and adds 1 to its index. This means that subsequent calls to morePermutations() will return false from here on out. This makes sense: there is exactly one permutation of a one-letter word -- itself. So far so good.
What about N-letter words, where N is 2 or more? Here, think about what the PermuteString object is tasked to do: return every permutation of its letters one by one, and notify its caller when no more permutations remain. The way it will do this is to designate one letter as the 'current' one, and use a child PermuteString to generate every possible permutation of its 'other' letters. On each iteration, it returns a string consisting of the current letter first, followed by some combination of its other letters.
How it actually goes about doing this is where things get pretty awful. Recall that at construction time, every PermuteString object has an index pointing at its first letter plus a child PermuteString for generating permutations of its 2nd through last letters. So, on each call to nextPermutation()
- First, it computes and stores in "r" the next permutation it will return. That's simply the current index letter plus the next permutation of its 'other' letters. Simple enough.
- Then, it takes a peek at its child PermuteString to see whether or not it has more substring permutations to give us. If it does, then this call to nextPermutation() is essentially complete: it returns "r" and exits.
- If, however, the child PermuteString is out of bullets, so to speak, then the parent knows that all permutations for its current starting letter have been generated. It advances its index to the next letter. If it has reached the end of its word, then all its permutations have been exhausted; note that all subsequent calls to morePermutations() will now return false. If not, then the object knows that it has to start generating permutations with its new starting letter. To do that, it needs to create a brand new substring generator consisting of all the other letters in its original word -- those from position 0 to the index letter it just finished with, plus those from the next letter to the end of the word. That's what "tailString" (a horribly named variable) computes, and the next line creates the PermuteString permutator for those other letters.

It's a perfectly good example of self-modifying recursive objects. Why is this lousy real-word code? Sheesh, there are a lot of reasons. Its variables are named very obliquely. It changes the value of substringGenerator in the middle of a (recursive) loop whose if condition checks if it is done. A call to nextPermutation() after the end is reached will result in a random out-of-bounds exception rather than a meaningful one. And so on, and so forth. But, the recursion itself is logical, and it's well worth understanding how it works. Cheers!

Permuting String in Java. Explain please?

Answers (2)

Related Questions