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!!!!!
source to share
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.
source to share
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 permutationsxample
, -
x
and one of the possible permutationseample
- 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.
source to share