java - 字谜算法说明

Question

我是这个论坛的新手，想问一个问题。我见过很多人问关于字谜的问题，但我的问题与这个特定的算法有关。我看到了使用递归技术生成字谜的算法，但该算法的一部分对我来说不是很清楚。我想就为什么采取该特定步骤寻求帮助。这个算法大纲来自Programming Interview Exposed。这是算法:

If you are past the last position
   print string and return
Otherwise
   For each letter in the input string
       If it is marked used, skip to the next letter
       Else place the letter in current position
   - Mark the letter used
   - Permute remaining letters staring at current position+1
   - Mark the letter as unused

下面是相同的代码:

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??
    }
}

在代码解释中提到，当递归调用返回时，最后一个字符只是通过减小缓冲区大小而被丢弃。我不明白为什么我们要删除最后一个字符？有人可以请指导。谢谢!!!!!!

Answer 1

还原 out.append(in[i]); 的效果(添加一个字符)并在 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
}

就这么简单。