计算数组的所有排列

Question

我正在尝试编写一种方法来将数组置换为所有可能的排列。我将每个数组以ArrayList的形式，翻转两个元素，然后将ArrayList返回到ArrayList of ArrayList。如果我在翻转两个元素后将每个数组打印到屏幕上，则按预期进行打印。[1,2,3]前两个元素翻转打印为[2,1,3]，但当我将置换的ArrayList添加到另一个ArrayList时，它们都打印为[1,2,3]

代码：

public static void arrays() {
    
    //convert the input Lists to ArrayLists
    ArrayList<Integer> a = new ArrayList<Integer>();
    a.add(1);
    a.add(2);
    a.add(3);
    //ArrayList<Integer> b = new ArrayList<Integer>(B);
    
    //an array with 3 elements will have 1 * 2 * 3 permutations
    Integer numberOfPossiblePermutations = numberOfPermutations(a);
    
    ArrayList<ArrayList<Integer>> allPermutations = new ArrayList<ArrayList<Integer>>();
    allPermutations.add(a);
    
    System.out.println("The properly rearranged arrays");
    while (allPermutations.size() < numberOfPossiblePermutations) {
        //get the last array in the list of arrays
        ArrayList<Integer> lastArray = allPermutations.get(allPermutations.size()-1);
        ArrayList<Integer> arrayToAdd = lastArray;
        
        for (int i=0; i+1<lastArray.size(); i++) {
            //flip two elements in the array
            
            int x = lastArray.get(i);
            int y = lastArray.get(i+1);
            arrayToAdd.set(i+1, x);
            arrayToAdd.set(i, y);
            System.out.println(arrayToAdd);
            allPermutations.add(arrayToAdd);
        }
        
    }
    
    System.out.println();
    System.out.println("but when I add each ArrayList to another ArrayList they are coming out like this");
    
    for (int i=0; i<allPermutations.size(); i++) {
        System.out.println(allPermutations.get(i));
    }
    
}

//accepts an array and returns the possible number of permutations
public static Integer numberOfPermutations(ArrayList<Integer> a) {
    Integer numberOfPermutations = 1;
    for (int i=1; i<=a.size(); i++) {
        numberOfPermutations *= i;
    }
    return numberOfPermutations;    
}

输出：

>

正确重新排列的数组

[2, 1, 3]

[2, 3, 1]

[3, 2, 1]

[3,1,2]

[1,3,2]

[1, 2, 3]

但是，当我将每个ArrayList添加到另一个ArrayList时，结果是这样的

[1, 2, 3]

[1, 2, 3]

[1, 2, 3]

[1, 2, 3]

[1, 2, 3]

[1, 2, 3]

[1, 2, 3]

Answer 1

您只与单个ArrayList实例交互，但以不同的名称调用它。因此，当您打印它时，您在该对象生命周期的不同阶段打印它，但它仍然是同一个实例。

这一行：

ArrayList<Integer> arrayToAdd = lastArray;

不复制对象；它只是给同一个对象一个不同的名称。您需要显式复制它。例如：

ArrayList<Integer> arrayToAdd = new ArrayList<Integer>();
arrayToAdd.addAll(lastArray);