0

我正在做一个项目。我在 Interwebz 上找到了有关排列的代码。我想用它作为编写我自己的代码的基础。但是，我真的不明白代码中发生了什么。有人可以帮我解释一下代码到底在做什么吗？

public void permutations(String prefix, String s) {
    int n = s.length();
    if (n == 0)
        System.out.println(prefix);
    else {
        for(int i = 0; i < n; i++){
           permutations(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, n));
        }
    }
}
4

4 回答 4

2

该方法permutations接受一个字符串prefix和一个字符串s作为其参数。int类型n被设置为 String 的长度s。（字符串的长度是它包含多少个字符）。

现在我们继续讨论if-else语句。该if语句是说，如果 的长度s为 0，即s是一个空白字符串并且不包含任何信息，那么我们只是将字符串打印prefix到控制台。然后该方法将跳过该else部分并执行该permutations方法之后的代码。

如果不满足该if语句的条件，我们将运行该else语句，对于 String 中的每个字符s，我们将在 的末尾追加（添加）该字符，prefix例如，如果prefix最初是“hello”字符是“U”，我们会prefix变成“helloU”。在我们完成追加所有字符后s，我们将使用结果作为新prefix字符串。

对于另一个参数 String s，我们将参与 String 的一部分，从字符 0（包括）到位置处的字符i（不包括）。请注意，字符串索引从 0 开始，一直到 (字符串的长度 - 1)。我们还将字符串的一部分从位置 i + 1（包括）处的字符到 String 中的最后一个字符s。我们将使用这个结果作为新的s字符串。

然后我们将再次调用该方法，然后如果满足else条件，该方法将使用新定义的字符串再次执行。这将继续循环，直到else条件不满足，此时方法将停止运行，我们将继续执行下一段代码（如果存在）。

于 2012-12-06T00:51:21.053 回答
2

p(String prefix, String s)取出 1 个字符s并将其添加到prefix并递归地继续直到s为空。

该s.charAt(i), s.substring(0, i) + s.substring(i+1, n)部分从 中提取一个字符s。假设s = "Magic!"，i = 3然后charAt(i) = 'i'，s.substring(0, i) = "Mag"和s.substring(i+1, n) = c!"。这分裂Magic!成iand Magc!。下次在循环i = 4中将导致c+ Magi!。因为它对每个字符中的s每个字符都这样做，所以在递归步骤之一中将位于前面。

调用层次结构看起来像这样

                                  / p("ab", "c") - "abc"
                 /- p("a", "bc") x
                /                 \ p("ac", "b") - "acb"
               /
              /                   / p("ba", "c") - "bac"
p("", "abc") x ---- p("b", "ac") x
              \                   \ p("bc", "a") - "bca"
               \
                \                 / p("ca", "b") - "cab"
                 \- p("c", "ab") x
                                  \ p("cb", "a") - "cba"

                 ^-- 1st for loop  ^- 2nd for      ^- 3rd one prints
于 2012-12-06T01:31:18.310 回答
1

permutations(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, n));

实际上，这个置换算法使用的思想是

Switching current character with ith character.

假设我们有一个字符串abc。所以它的排列是：

abc, acb, bac, bca, cab, cba

我们可以发现，这只是acb切换b并带有前缀c。而这只是切换并带有前缀。abcabcacabacb

然后我们就用同样的思路递归解决置换问题。

于 2012-12-06T00:36:46.093 回答
1

这是一些非常令人困惑的代码，原因有两个：

  1. 参数：您应该在第prefix一个参数中使用空字符串调用此函数，例如permutations("", "ab")打印"ab".
  2. 第二个参数中的递归调用s.substring(0, i) + s.substring(i+1, n)：注意javaString.substring(x,y)不会包含第y个字符。所以这相当于s删除了第 y 个字符。

现在想想当你单步执行for循环时会发生什么：第一个参数与ie""连接，第二个参数与删除的第一个字符 ie连接。在下一个递归子调用中，变为，第二个参数变为空字符串。所以基本情况被击中，我们打印结果。"a""a"s"b"prefix"ab"""n == 0"ab"

现在我们进入 for 循环的下一次迭代，i == 1. 现在我们传入"b"递归子调用的第一个参数和"a"第二个参数。在下一个递归子调用中prefix变为"ba"ands.length为 0，所以又是基本情况： print "ba"。

这很聪明，但难以理解。

于 2012-12-06T01:01:03.437 回答