0

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());
}
}
Improve this question
4
  • 2
    Java is a clear, declarative language. As such, it does exactly what it looks like it's doing (well, we like to think so). You would be better served by familiarizing yourself with the language first. If you are confused by the paths the code takes, experiment a little -- trace it in a debugger, print information here and there, write a string on a piece of paper and apply the algorithm by hand, stepping through the code and writing out strings along the way. Commented Aug 6, 2013 at 15:58
  • There is room in the world for higher level descriptions than Java source code. While Java is very precise, without some other-than-java guidance, it would be hard to see a forest among all the trees. Commented Aug 6, 2013 at 16:03
  • It's not to do with me being unfamiliar with Java - I'm closer to 'intermediate' than 'absolute beginner' - it's just that I cannot understand how the recursion does its job in this particular example. Commented Aug 6, 2013 at 16:16
  • @AlexanderPower That's why tracing through it by hand is important. That should clarify what's happening for you. To trace recursions, I find the following helpful: Every time you call the function recursively, start tracking state on a new piece of paper and place the previous sheet on top of a stack of papers off to the side. When you get to a return statement, throw away the current sheet, pick up the sheet of paper on top of your stack and plug in the return value where the recursive call took place. Commented Aug 6, 2013 at 19:06

2 Answers 2

Reset to default
2

To generate permutations, there are typically two approaches

  1. Ranking and Unranking
  2. Incremental change methods

This routine uses an incremental change method. Basically, it selects some order of elements (the same order as the starting), and then moves up and down a tree of options, by shuffling one element, then recursively generating the sub permutation required below it.

permutation(everything) expands to

(select 1) + permutation(everything but 1)
(select 2) + permutation(everything but 2)
(select 3) + permutation(everything but 3)
...
(select n) + permutation(everything but n)

and

permuation(one item) expands to
(select item)

This is controlled by morePermutations() which returns false if there is only one element in the nested PermuteString class.

If there are two or more characters in the PermuteString, index keeps track of the selected item, and a new sub-PermuteStrings are constructed as index is moved.

When asked for the next permutation, the requests travel down the nested PermuteStrings until a string detects that it's child doesn't have a "next" permutation, so that parent updates it's index, and swaps out it's previous child with a new one that now only lacks the "new" index character.

(for completeness sake, a high level description of ranking and un-ranking)

Ranking and unranking work differently. One knows the count of all possible permutations of a particular size, so you create a map of permutations to an "index" within that size. Then you create a reverse map from that index to a value. A high level example would then look like

the entire map for 3 items (6 permutations) would look like

(a, b, c) <=> 0
(a, c, b) <=> 1
(b, a, c) <=> 2
(b, c, a) <=> 3
(c, a, b) <=> 4
(c, b, a) <=> 5

(a, b, c) => 0
to find the next, just add one
0 + 1 => 1
1 => (a, c, b)

There are formal mathematical means for mapping an unmapping permutations without maintaining a map in memory, but they are often not used because the index grows quite quickly, often creating issues as the number exceeds MAX_INT.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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!

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.