java - 我的字符串排列算法不起作用

Question

我写了一个解决字符串排列算法的算法。它有问题，在某处打印错误的输出。我已针对不同的输入多次遍历我的代码，但我找不到我犯了什么错误。

谁能解释一下我哪里做错了？

public static void main(String args[]) throws Exception {

    String str1 = "eat";
    int len = str1.length();
    char[] str = str1.toCharArray();
    recurPerm(str,0,len);
}
static void recurPerm(char[] str, int strstartind, int sz) {

    for(int i = strstartind; i < sz; i++){
        if(i > strstartind) {

            char temp = str[strstartind];
            str[strstartind] = str[i];
            str[i] = temp;

            recurPerm(str, strstartind + 1, sz);
        }
        else {
            recurPerm(str, strstartind + 1, sz);
        }
    }
    if(strstartind >= sz){
        System.out.println(str);
    }

    return;
}

输出

eat
eta
tea 
tae
eat
eta

但是正确的输出是

eat eta aet ate tae tea

我也试过调试。我发现调试起来太难了，因为涉及到递归。

Answer 1

你应该恢复递归的原始状态，否则你会一直混淆给定的参数。函数参数“strstartind”仅指示要选择的正确字符，如果原始“str[]”未更改，但是您在以下位置覆盖了原始“str[]”:

    str[strstartind] = str[i];
    str[i] = temp;

这里有一个可行的解决方案，可以恢复递归参数:

public class DemoApplicationTests {

public static void main(String args[]) throws Exception {

    String str1 = "eat";
    int len = str1.length();
    char[] str = str1.toCharArray();
    recurPerm(str, 0, len);
}

static void recurPerm(char[] str, int strstartind, int sz) {

    for (int i = strstartind; i < sz; i++) {
        char temp = str[strstartind];
        str[strstartind] = str[i];
        str[i] = temp;
        recurPerm(str, strstartind + 1, sz);
        //restore state
        str[i] = str[strstartind];
        str[strstartind] = temp;
    }
    if (strstartind >= sz) {
        System.out.println(str);
    }

    return;
}
}