java - 递归方法中 int[] 的 ArrayList

Question

我有一个要为学校做的项目，其中我必须使用递归方法来计算某些数字之间的所有切换可能性。 即:[1,2] => 1,2 和 2,1。

所以我使用了这种方法，当我在控制台上打印解决方案时，它似乎工作正常，但是当我想将选项卡存储在 ArrayList 中时(我稍后需要使用它们)，它总是会添加相同的顺序。在我的示例中，它会添加 1,2 和 1,2，而不是 1,2 和 2,1。

这是我的代码:

public  static void permute(int start, int[] input, ArrayList <int[]> al) { 
    //This method is recursive, it will open multiple instances of the input tab by calling itself and modify them, then stock tab in ArrayList when the operations are done for this tab.
    //ArrayList must be empty.

    //Printing tab if iterations for that specific tab are done
    if (start == input.length) {
        al.add(input);
        ////////////////////////////////
        // For printing tabs in console.
        // for(int x: input){
        // System.out.print(x);
        // }
        // System.out.println("");
        ////////////////////////////////
    //End the specific tab loop when it's printed 

    return;
    }
    for (int i = start; i < input.length; i++) {
        // Changing numbers
        int temp = input[i];
        input[i] = input[start];
        input[start] = temp;

        //////////////////////////////////////////////////
        // Tests to see algorithm steps
        //
        // System.out.print("temp : " + temp + " ... ");
        // System.out.print("i : "+i + " ... ");
        // System.out.print("start : " + start);
        // System.out.println("");
        // System.out.print("---");
        // for(int x: input){
        //  System.out.print(x);
        // }
        // System.out.println("");
        //////////////////////////////////////////////////

        //Changing numbers
        permute(start + 1, input, al);

       // Changing numbers
        int temp2 = input[i];
        input[i] = input[start];
        input[start] = temp2;

}

}

我使用 start = 0，input = {1,2,3}，并且在方法开始之前 ArrayList 为空。

希望您能帮忙，谢谢!

Answer 1

问题是您将对数组的引用添加到 ArrayList 中，然后在算法中不断更改该引用。

到最后，您将拥有同一数组的 perm(N) 个副本。

您所要做的就是将数组的深层复制添加到 ArrayList 中，如下所示:

al.add(Arrays.copyOf(input, input.length));

而不是

al.add(input);

打印结果 ArrayList 将产生以下输出:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]