Java实现数组全排列时ArrayList存储结果全相同问题

核心由Java对象引用机制导致：

• 代码中ArrayList<Integer> arrayToAdd = lastArray;未创建新的ArrayList对象，仅将原有列表的内存引用赋值给新变量。后续存入allPermutations的所有元素，本质都指向最初创建的a列表对象，没有存储任何独立的排列副本。
• 交换元素时修改的始终是同一个列表对象，交换后立即打印输出的是对象当时的瞬时状态，因此看起来结果正确；等整个循环执行完毕，这个列表已经被多次交换回初始状态[1,2,3]，此时遍历外层结果集，所有引用都指向这同一个已回到初始值的对象，自然全部输出初始内容。
• 额外说明：当前采用相邻交换循环生成排列的逻辑本身存在缺陷，会生成重复排列，也无法覆盖所有合法全排列，标准无重复全排列一般通过回溯交换法实现。

1. 每次生成新排列准备存入结果集前，必须基于当前列表创建独立副本，禁止直接添加原对象引用。将原赋值语句替换为副本创建逻辑：

   // 错误写法：ArrayList<Integer> arrayToAdd = lastArray;
   // 正确写法：创建独立的列表副本
   ArrayList<Integer> arrayToAdd = new ArrayList<>(lastArray);
   

2. 替换原有错误的排列生成逻辑，采用标准回溯实现全排列，完整可运行修正代码如下：

   import java.util.ArrayList;
   import java.util.Collections;
   
   public class PermutationTest {
       public static void arrays() {
           ArrayList<Integer> a = new ArrayList<>();
           a.add(1);
           a.add(2);
           a.add(3);
           ArrayList<ArrayList<Integer>> allPermutations = new ArrayList<>();
           backtrack(a, 0, allPermutations);
   
           System.out.println("全排列结果：");
           for (ArrayList<Integer> perm : allPermutations) {
               System.out.println(perm);
           }
       }
   
       private static void backtrack(ArrayList<Integer> nums, int index, ArrayList<ArrayList<Integer>> res) {
           if (index == nums.size()) {
               res.add(new ArrayList<>(nums));
               return;
           }
           for (int i = index; i < nums.size(); i++) {
               Collections.swap(nums, index, i);
               backtrack(nums, index + 1, res);
               Collections.swap(nums, index, i);
           }
       }
   
       public static Integer numberOfPermutations(ArrayList<Integer> a) {
           Integer numberOfPermutations = 1;
           for (int i = 1; i <= a.size(); i++) {
               numberOfPermutations *= i;
           }
           return numberOfPermutations;
       }
   }
   

修正后运行可以得到全部6个无重复、无遗漏的全排列结果，不会再出现所有元素均为初始值的问题。

内容的提问来源于stack exchange，提问作者user1940576