字谜算法澄清

Question

我是这个论坛的新手，想问一个问题。我看到许多人在问变位词的问题，但我的问题与这个特定的算法有关。我看到了这个使用递归技术生成变位词的算法，但其中的一部分对我来说不太清楚。我想寻求帮助，了解为什么要采取这个特定的步骤。这个算法大纲来自《编程面试揭秘》。以下是这个算法：

如果您已经过了最后一个位置
   打印字符串并返回
否则
   对于输入字符串中的每个字母
       如果它被标记为使用过，则跳过下一个字母
       否则将该字母放在当前位置
   - 标记该字母已使用
   - 从当前位置+1开始排列剩余字母
   - 将该字母标记为未使用

以下是相同的代码：

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

在代码说明中提到，当递归调用返回时，通过减少缓冲区大小来简单地删除最后一个字符。我不明白为什么我们要删除最后一个字符？有人可以指导一下吗？谢谢！！！

- Shyna

---

哇，那个算法比我平常看到的用于检查变位词的算法要复杂得多。我习惯于看到“将两个单词分割成字母并排序，如果结果匹配，则它们是变位词”。 - Mr. Llama

我认为这是一个字谜生成算法，而不是检查算法 :) - cerkiewny

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
}

这很简单。

- biziclop

---

谢谢biziclop！假设我有一个字符串abc，我需要获取它的变位词。所以这里是递归调用-对于以a开头的变位词，我们得到3个递归调用：doPermute（in，out，3，1），dopermute（in，out，3，2），doPermute（in，out，3，3）。当长度和级别变为时，递归调用返回，现在每个字符都标记为未使用，并清除该字符的输出缓冲区，直到第一个递归调用即do permute（in，out，3，1）。然后我们将开始以b开头的变位词，并将使用已经清除的相同缓冲区out。这正确吗？还是还有什么遗漏？ - Shyna

Answer 2

该算法正在执行以下操作：

• 从所有字母中选择起始字母。
• 如果我们已经设置了所有字母，则打印可能的一个变位词。
• 否则，我们将其标记为已使用，并需要将剩余字母的排列添加到末尾。

让我们来看个例子：

我们有以下字母：

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

让我们选择第一个字母：

它可以是：

• e 和 xample 的一种可能的排列之一，
• x 和 eample 的一种可能的排列之一，
• 等等。

当我们选择所有字母时，我们将打印创建的单词。

你也可以把它看作是一棵决策树， 首先你从n个字母中选择一个，然后你从剩下的字母中选择一个，当你选择完所有的字母（到达了树的底部并获得了唯一的变位词），因为在每一步中你都有一个for循环（所以对于所有可能的决策，探索树的低层），你将得到每个组合并打印出来。

我真的希望这能帮到你。

- cerkiewny