使用递归实现字符串排列

Question

我是一名Java初学者，正在尝试从Java编程书籍中进行字符串排列练习。我定义了两个方法：

public static void displayPermutation(String s)
public static void displayPermutation(String s1, String s2)

第一种方法只需调用displayPermutation(" ", s)即可。第二种方法使用循环将s2中的字符移动到s1中，并使用新的s1和s2进行递归调用。基本情况是s2为空，将s1打印到控制台。

有人能帮我找到以下代码的问题吗？

这是一个例子：

 public static void displayPermutation(String s) {
            displayPermuatation("", s);
        }

    private static void displayPermuatation(String s1, String s2) {
        //base case: when s2 is empty, print s1
        if (s2.isEmpty()) {
            System.out.println(s1);
        }
        else {          
        for (int i = 0; i < s2.length(); i++) {
                        //move a char from s1 to s2, and recursively invokes it with 
                        //new s1 and s2
            s1 = s1 + s2.charAt(i);
            s2 = s2.substring(0, i) + s2.substring(i+1);
            displayPermuatation(s1, s2);
        }
    }
   }

如果 s = "abc"，则只打印: abc acb

在第一次调用 displayPermuatation("", "abc") 时，似乎没有完成 for 循环....有任何意见吗？

感谢下面的所有评论。我认为我犯的错误是将对象作为参数传递给方法实际上是传递引用。它不像原始数据（按值传递）。当更改对象时，它将影响使用该对象的后续方法调用。

- Vortex

---

当s="abc"时，正确的结果应该是什么？ - fmodos

抱歉，我忘记在文章中添加它了。预期结果是：abc、acb、bac、bca、cab、cba。 - Vortex

你尝试过在调试器下运行它，或者在displayPermutation例程中插入打印输出以查看它实际执行的操作（而不是你假设的操作）吗？我认为你可以通过这些信息自己解决这个问题。 - keshlam

你正在循环内给s2赋新值，同时检查它的长度(s2.length())。这可能会导致问题。 - regulus

@keshlam 是的，我确实尝试了调试器，并发现它在调用displayPermuatation（“”，“abc”）的for循环中没有完成。 - Vortex

Answer 1

不要在循环中更改s1和s2，这会导致错误。只需将这些定义作为参数传递给递归函数即可。像这样：

.
.
for (int i = 0; i < s2.length(); i++) {
        displayPermuatation(s1 + s2.charAt(i), s2.substring(0, i) + s2.substring(i+1));
    }
.
.

- Mehmet Sedat Güngör

Answer 2

您的代码问题在于您在循环中更改了s1和s2的值，这会影响循环中后续的迭代。请看下面的代码，我已经解决了这个问题。

public static void displayPermutation(String s) {
    displayPermuatation("", s);
}

private static void displayPermuatation(String s1, String s2) {
    // base case: when s2 is empty, print s1
    if (s2.isEmpty()) {
        System.out.println(s1);
    } else {
        for (int i = 0; i < s2.length(); i++) {
            // move a char from s1 to s2, and recursively invokes it with
            // new s1 and s2
            displayPermuatation(s1 + s2.charAt(i), s2.substring(0, i) + s2.substring(i + 1));
        }
    }
}

- Hemant

---

谢谢！那个有效！我将编辑我的帖子，添加一些注释以供将来参考。 - Vortex

Answer 3

在循环中不要更改s1和s2的原始值：

private static void displayPermuatation(String s1, String s2) {
    //base case: when s2 is empty, print s1
    if (s2.isEmpty()) {
        System.out.println(s1);
    }
    else {       
    for (int i = 0; i < s2.length(); i++) {
                    //move a char from s1 to s2, and recursively invokes it with 
                    //new s1 and s2
        string new_s1 = s1 + s2.charAt(i);
        string new_s2 = s2.substring(0, i) + s2.substring(i+1);
        displayPermuatation(new_s1 , new_s2 );
    }
}

- d.raev