java - 递归地遍历数组的所有排列

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 编写它，但我会理解 C、javascript 或其他任何语言的示例，只要它不使用 Java 中不可用的一些库技巧。

Answer 1

需要三个更正才能工作:

• 仅在 (start == permus.length-1) 时打印，否则你会看到重复项
• 从 i = start 开始 for 循环，而不是 i = start + 1
• 递归调用 testPermu(start + 1); 而不是 testPermu(i);