递归遍历数组的所有排列

Question

我试图编写一个递归函数来产生数组的所有排列。

static int permus[] = new int[] { 1, 2, 3, 4, 5 };


static void testPermu(int start)
{
    // Print it
    System.out.println(Arrays.toString(permus));

    int k;
    for (int i = start + 1; i < permus.length; i++) {
        // swap
        k = permus[start];
        permus[start] = permus[i];
        permus[i] = k;

        testPermu(i);

        // unswap
        k = permus[start];
        permus[start] = permus[i];
        permus[i] = k;
    }
}

它会作为调用，testPermu(0)并应产生所有排列，但是不起作用。我该如何解决？

它需要递归，每次调用该函数时，都应该获得新的排列。

现在的输出是

[1、2、3、4、5]
[2，1，3，4，5]
[2、3、1、4、5]
[2，3，4，1，5]
[2、3、4、5、1]
[2、3、5、4、1]
[2，4，3，1，5]
[2，4，3，5，1]
[2、5、3、4、1]
[3，2，1，4，5]
[3，2，4，1，5]
[3，2，4，5，1]
[3，2，5，4，1]
[4，2，3，1，5]
[4，2，3，5，1]
[5，2，3，4，1]

您可以看到缺少许多排列。

我正在用Java编写它，但是只要不使用Java中没有的一些库技巧，我就会理解用C，javascript或其他语言编写的示例。

Answer 1

这是一个完整的示例：

package eric.math;

import java.util.Arrays;

public class Permute {
    // swap 2 elements of an array,
    void swap(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    /**
     * print permutations of array
     * @param arr
     *            original int array,
     */
    void permute(int[] arr) {
        permute(arr, 0, arr.length - 1);
    }

    /**
     * print permutations of array
     * 
     * @param arr
     *            original int array,
     * @param i
     *            start index
     * @param n
     *            end index
     */
    void permute(int[] arr, int i, int n) {
        int j;
        if (i == n)
            System.out.println(Arrays.toString(arr));
        else {
            for (j = i; j <= n; j++) {
                swap(arr, i, j);
                permute(arr, i + 1, n);
                swap(arr, i, j); // backtrack
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = { 1, 2, 3 };
        new Permute().permute(arr);
    }
}