字谜算法说明

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

算法正在执行以下操作：

从所有字母集中，让我们选择起始字母。
如果我们已经设置好所有这些，那么我们将打印其中一个可能的字谜。
否则，那么我们将其标记为已使用，我们需要将剩余字母的排列添加到末尾。

让我们举个例子：

我们有以下信件：

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

让select第一个字母：

它是：

e 和 xample,
x 和 eample
等等

当我们 select 所有皮革时，我们将打印 created 这个词。

你也可以把它想象成一个决策树，首先你 select n 个字母中的一个，然后你 select 剩下的一个，一旦你 select 编辑了所有字母（你到达了树的底部并得到了自己的一个独特的字谜）因为在每个步骤中你都有一个 for 循环（所以对于所有可能的决定探索树的较低级别）你将得到每个组合并打印它。

我真的希望这对您有所帮助。

Answer 2

恢复 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
}

就这么简单

字谜算法说明

Anagram Algorithm Clarification

java

algorithm

anagram