无法理解字符串排列 Java 代码

Question

我有这个工作代码可以不重复地打印字符串排列，但我无法理解它在逻辑上是如何工作的。任何建议都会很有帮助。

private static void permutation(String input, String sofar) {
        if (input.equals("")) {
            System.out.println(count + " " + sofar);
            count++;
        }
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (input.indexOf(c, i + 1) != -1)
                continue;
            permutation(input.substring(0, i) + input.substring(i + 1), sofar+c);
        }
    }

函数调用：

String input = "ABBCD";
permutation(input, "");

Answer 1

 for (int i = 0; i < input.length(); i++) {

上面的 for 循环很神奇

输入ABCD

迭代次数

输入：BCD sofar：A ....递归继续

输入：ACD sofar：B ....

输入：ABD 到目前为止：C ....

输入：ABC 到目前为止：D .....

希望对您有所帮助

Answer 2

if (input.equals("")) {
     System.out.println(count + " " + sofar);
     count++;
}

由于输入不是""，这一步通过了。请注意，您可以在此处简单地使用 input.empty()。这里唯一要记住的是 count 没有递增。

for (int i = 0; i < input.length(); i++) {

这将遍历 input

的所有字符

char c = input.charAt(i);
if (input.indexOf(c, i + 1) != -1)

检查下一个字符是否等于当前字符，如果是，则使用continue关键字直接跳转到下一个iteration（下一个字符）。

如果没有，那么它会调用方法（我们称之为recursivity），传入没有当前char的字符串。但是把它还给 sofar.

permutation(input.substring(0, i) + input.substring(i + 1), sofar+c);

现在在输入为空的情况下，

将打印非不同 character 的计数 + 所有这些 character。

Answer 3

请记住递归通常是一个停止条件，并且在递归有效的假设下尝试使用递归调用解决较小的问题。

我已经对代码进行了注释，因此您可以将其替换为您的副本，以便在您返回时跟踪它在做什么。理解后添加您自己的评论，因为它们将帮助您了解发生的情况：

第1部分：基本条件/停止条件：

if (input.equals("")) {
    System.out.println(count + " " + sofar);
    count++;
}

这部分停止递归并returns一个结果，基本情况是一个空字符串，它有一个也是空字符串的单一排列。

第 2 部分： 迭代较小的问题。

 for (int i = 0; i < input.length(); i++) {
    char c = input.charAt(i);
    // ...
    permutation(input.substring(0, i) + input.substring(i + 1), sofar+c);
}

这部分使用递归调用较小的（一个字符）字符串来解决问题。它调用相同的字符串，省略它在生成的任何后续结果之前添加的字符。我们知道调用会生成所有排列（这是我们的假设）。所以我们现在知道递归的作用了。

第 2.1 部分： 去重 "if"：

这可能是这里最棘手的部分...

if (input.indexOf(c, i + 1) != -1)
    continue;

我们来解决这个问题。它的意思是："try and find a character the same as the one selected, and if one exists, skip this iteration and it's generated solutions".

想想像 "ABBA" 这样的词，它会跳过第一个 "A" 和 "B"，但不会跳过最后一个。为什么？好吧，因为相似字符的顺序无关紧要（如果我们标记字符 A1 B1 B2 A2，现在替换它们：A2 B2 B1 A1，这仍然是同一个词，所以像 "AA" 这样的词只有一个排列，因为 A1 A2 与A2 A1.

获取 last 个字符更容易，因为我们不需要维护我们已在此迭代中使用的字符列表。

带有基本注释的完整代码：

private static void permutation(String input, String sofar) {

        if (input.equals("")) {
            // this is the stop condition
            // the only permutation of "" is ""
            System.out.println(count + " " + sofar);
            // this counts how many permutations were outputted.
            count++;
        }

        for (int i = 0; i < input.length(); i++) {
            // this loop basically means "take every
            // possible character, and append permutations of all
            // other characters to it.
            char c = input.charAt(i);
            if (input.indexOf(c, i + 1) != -1)
                // this makes sure we only take a single "A" or "B"
                // character in words like "ABBA", since selecting
                // the same character would create duplicates
                continue;

            // this creates a new string without the selected character
            // and under the assumption the recursion works
            // appends all permutations of all other characters
            // to it
            permutation(input.substring(0, i) + input.substring(i + 1), sofar+c);
        }
    }

无法理解字符串排列 Java 代码

Not able to understand string permutation Java code

java

string

permutation