Anagram算法澄清

Question

我是这个论坛的新手，我想问一个问题。我见过很多人在字谜上提问，但我的问题与这个具体的算法有关。我看到了这个算法，它使用递归技术生成字谜，但是这个算法的一部分对我来说不是很清楚。我想就采取这一具体步骤的原因寻求帮助。本算法大纲是从编程访谈中暴露出来的。以下是算法：

如果你已经过了最后一个职位 间接打印字符串和返回 否则 对应输入字符串中的每个字母 .=‘1’>如果标记使用，跳到下一个字母 将字母置于当前位置 标记所用的字母 几乎不可能保持不变的剩余字母盯着当前的position+1 . unused =‘unused 2’>标记为未使用的字母

下面是相同的代码：

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
}

事情就是这么简单。

Answer 2

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

• 从所有字母的集合中，我们选择起首字母。
• 如果我们已经把它们全部设置好了，那么我们就打印一个可能的字谜。
• 否则，我们将此标记为已使用的，我们需要将其余字母的排列添加到末尾。

下面让我们举个例子：

我们有以下信件：

e，x，a，m，p，l，e

让我们选择第一个字母：

它要么是：

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

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

你也可以把它想成一个决策树，首先你选择一个n个字母，然后你从剩下的字母中选择一个，一旦你选择了所有的字母(你到了树的底部，得到了一个独特的字谜)，因为在每一步你都有一个for循环(所以对于所有可能的决策，探索树的较低的层次)，你将得到每个组合并打印它。

我真的希望这能帮上忙。