Clever Geek Handbook

Refinement of the anagram algorithm

I am new to this forum and wanted to ask a question. I have seen several people asking questions about anagrams, but my question is related to this particular algorithm. I have seen this algorithm that uses the recursion method to generate anagrams, but part of this algorithm is not very clear to me. I wanted to ask for help in terms of why this particular step was taken. This algorithm is described in the Programming Survey section. Here's the algorithm:

If you are behind the last position
      print string and return
  Otherwise
       for each letter in the input string
           If it is marked as used, go to the next letter
           Else place the letter at the current position
          - Mark the letter in use
          - Take over the remaining letters looking at the current position + 1
         - Mark email as unused

Here's the code for it:

void permute(String str){
    int length = str.length();
    boolean[] used = new boolean[length];
    StringBuffer out = new StringBuffer();
    char[] in = str.toCharArray();
    doPermute(in, out, used, length, 0);
}
void doPermute(char[] in, StringBuffer out, boolean[] used, int length,
    int level){
    if (level == length){
        System.out.println(out.toString());
        return;
    }
    for (int i = 0; i<length; i++){
        if (used[i]) continue;
        out.append(in[i]);
        used[i] = true;
        doPermute(in, out, used, length, level + 1);
        used[i] = false;
        out.setLength(out.length() - 1); // why are we reducing the size of out??
    }
}

The explanation of the code mentions that when the recursive call returns, the last character is simply discarded by decreasing the buffer size. I can't figure out why we are dropping the last character? Can anyone please help. Thank!!!!!

+3


source to share


2 answers


To revert the effect out.append(in[i]);

(which adds a character) and restore the buffer to the same state after each iteration of the loop for

.

for (int i = 0; i<length; i++){
    if (used[i]) continue;
    out.append(in[i]); // try adding the ith letter
    used[i] = true;    // and mark it as used
    doPermute(in, out, used, length, level + 1); // do all the permutations for the remaining letters
    used[i] = false;                 // undo what we did
    out.setLength(out.length() - 1); // at the start of the loop
}


It is so simple.

+2


source


The algorithm performs the following actions:

  • Select the initial letter from the set of all letters.
  • If we have all of them installed, then we print one of the possible anagrams.
  • Otherwise, we mark it as used and we need to add the permutation of the remaining letters to the end.

So let's take an example here:

We have the following letter:

e, x, a, m, p, l, e

Lets you select the first letter:



his:

  • e

    and one of the possible permutations xample

    ,
  • x

    and one of the possible permutations eample

  • and etc.

When we select everything from leather, we will print the created word.

You can also think of it as a decision tree.First, you choose one of the n letters, then you choose one of the remaining ones, and after you have chosen all of them (you got to the bottom of the tree and got yourself one of the unique anagrams). because at each step you have a for loop (so for all possible solutions exploring the lower levels of the tree), you go to each combination and print it.

I really hope this helps.

0


source






More articles:


All Articles