生成字符数组的所有排列

Question

在阅读了许多关于“生成字符串排列”的帖子后，我尝试用Java编写它。

1）从第一个字符开始，与组合中的其他字符交换。

但是当我尝试使用递归实现时，对于长度为3的字符串，它只给出了两个字符串 :(。

public static void main(String[] args) {
    char a[]= "123".toCharArray();
    printPermutation(a,0);

}
private static void printPermutation(char[] a, int i) {
    if(i==a.length-1)
        System.out.println(new String(a));
    else{
        for(int x=i+1;x<a.length;x++)
        {
            swap(a,i,x);
            printPermutation(a,x );
            swap(a,i,x);
        }
    }
}
private static void swap(char[] a, int i, int x) {
        char t=a[i];
        a[i]=a[x];
        a[x]=t;
    }

我希望打印出6个字符串。

期望输出: 123， 132， 213， 231， 312， 321

- dead programmer

---

为了您自己的心理健康和周围人的健康，请使用更好的变量名称！合理地命名可以帮助您尽早发现错误，并使代码在休息后更容易阅读。 - JonK

你能提供样例代码的预期输出吗？ - Ruben Pirotte

如果您删除if和else子句，将会得到2个更多的输出。无论如何，正如JonK所说，请使用更好的变量名称。使用这些名称使您的算法难以理解。在printPermutation方法中，参数i是什么意思？ - Egl

Answer 1

方法printPermutation是你递归的核心。它没有正确捕获start和end索引。这很重要，因为你正在尝试以块为单位进行交换。

下面的更改应该使它能够正常工作。

public static void main(String[] args) {
    char a[]= "123".toCharArray();
    printPermutation(a, 0, a.length);
}

private static void printPermutation(char[] a, int startIndex, int endIndex) {
    if (startIndex == endIndex)//reached end of recursion, print the state of a
        System.out.println(new String(a));
    else {
        //try to move the swap window from start index to end index
        //i.e 0 to a.length-1
        for (int x = startIndex; x < endIndex; x++) {
            swap(a, startIndex, x);
            printPermutation(a, startIndex + 1, endIndex);
            swap(a, startIndex, x);
        }
    }
}

private static void swap(char[] a, int i, int x) {
    char t = a[i];
    a[i] = a[x];
    a[x] = t;
}

- JavaHopper

Answer 2

您的排列算法的总体思路是正确的，但是您忘记处理其中一些可能的情况。

首先。 在进入循环之前，您应该添加printPermutation(a, i + 1)。

其次。 在循环中调用printPermutation(a, i + 1)而不是printPermutation(a, x)。

public static void main(String[] args) {
    char a[]= "1234".toCharArray();
    printPermutation(a, 0);
}

private static void printPermutation(char[] a, int i) {
    if (i == a.length - 1) System.out.println(new String(a));
    else {
        printPermutation(a, i + 1);
        for (int x = i + 1; x < a.length; x++) {
            swap(a, i, x);
            printPermutation(a, i + 1);
            reswap(a, i, x);
        }
    }
}

private static void swap(char[] a, int i, int x) {
    char tmp = a[i];
    a[i] = a[x];
    a[x] = tmp;
}

private static void reswap(char[] a, int i, int x) {
    swap(a, i, x);
}

- mr.tarsa