含重复元素数组全排列：相邻元素去重失效问题咨询

问题背景 #

需求：给定一个可能包含重复元素的数组，返回其所有全排列（顺序不限）。

使用HashSet跳过重复元素的代码可正常运行：

package test;

import java.util.*; 

public class test {
      static ArrayList<ArrayList<Integer>> get_permutations(ArrayList<Integer> arr) {
            ArrayList<ArrayList<Integer>> res=new ArrayList<>();
            //Collections.sort(arr);
            helper(arr, 0, res);
            return res;
        }
        
        static void helper(ArrayList<Integer> arr, int pos, ArrayList<ArrayList<Integer>> res){
            int n=arr.size();
            if(pos>=n){
                res.add(new ArrayList<Integer>(arr));
                return;
            }
            
            Set<Integer> set=new HashSet<>();
            for(int i=pos; i<n; i++){
                //if(i>pos&&arr.get(i).equals(arr.get(i-1)))  
                if(!set.add(arr.get(i)))
                    continue;
                
                Collections.swap(arr, pos, i);
                helper(arr, pos+1, res);
                Collections.swap(arr, pos, i);
            }
        }
    // Driver code
    public static void main(String args[])
    {
        ArrayList<Integer> arr= new ArrayList<>(Arrays.asList(3,3,8,8,9,9,9));
        for(var v:get_permutations(arr)){
            System.out.println(v);
        }
    }
}

但先对数组排序、通过比较相邻元素跳过重复的代码，在测试用例[3,3,8,8,9,9,9]下无法正常工作：

import java.util.*; 

public class test {
      static ArrayList<ArrayList<Integer>> get_permutations(ArrayList<Integer> arr) {
            ArrayList<ArrayList<Integer>> res=new ArrayList<>();
            Collections.sort(arr);
            helper(arr, 0, res);
            return res;
        }
        
        static void helper(ArrayList<Integer> arr, int pos, ArrayList<ArrayList<Integer>> res){
            int n=arr.size();
            if(pos>=n){
                res.add(new ArrayList<Integer>(arr));
                return;
            }
            
            //Set<Integer> set=new HashSet<>();
            for(int i=pos; i<n; i++){
                if(i>pos&&arr.get(i).equals(arr.get(i-1)))  
                //if(!set.add(arr.get(i)))
                    continue;
                
                Collections.swap(arr, pos, i);
                helper(arr, pos+1, res);
                Collections.swap(arr, pos, i);
            }
        }
    // Driver code
    public static void main(String args[])
    {
        ArrayList<Integer> arr= new ArrayList<>(Arrays.asList(3,3,8,8,9,9,9));
        for(var v:get_permutations(arr)){
            System.out.println(v);
        }
    }
}

提问：这与子集问题的去重逻辑相反，输出存在重复项，请问遗漏了什么？

问题原因 #

核心问题是你在使用swap交换元素后，破坏了数组原本的有序性，导致相邻元素比较的逻辑失效：

• 子集问题中，我们按顺序选取元素，不会交换数组元素，排序后相同元素始终相邻，所以i>pos && arr.get(i).equals(arr.get(i-1))可以有效跳过同一层递归中重复的元素。
• 但全排列的swap操作会打乱排序后的数组，当你交换pos和i位置的元素后，后续递归返回再交换回来，此时数组中相同元素的位置已经不再连续，下一次循环时相邻比较就无法准确识别重复元素。

比如测试用例排序后是[3,3,8,8,9,9,9]，当第一次循环pos=0，i=1时，因为arr[1] == arr[0]会跳过；但如果i=2（元素8）交换到pos=0，递归返回后交换回来，此时数组回到有序状态，但如果后续i遇到另一个3，此时它的前一个元素可能已经不是3了，导致重复处理。

修正方案 #

如果要保留排序+去重的思路，不能依赖相邻元素比较，而是需要在**当前递归层（同一pos）**记录已经处理过的元素，避免重复。和HashSet方案类似，但可以结合排序优化，或者换一种不使用swap的全排列实现（用visited数组标记已使用元素）。

修正后的排序+去重代码（保留swap） #

我们可以在每一层递归中用一个局部的HashSet，记录当前pos位置已经用过的元素，和第一种方案逻辑一致，只是先排序（排序可以减少一些重复判断，但不是必须的）：

import java.util.*; 

public class test {
      static ArrayList<ArrayList<Integer>> get_permutations(ArrayList<Integer> arr) {
            ArrayList<ArrayList<Integer>> res=new ArrayList<>();
            Collections.sort(arr);
            helper(arr, 0, res);
            return res;
        }
        
        static void helper(ArrayList<Integer> arr, int pos, ArrayList<ArrayList<Integer>> res){
            int n=arr.size();
            if(pos>=n){
                res.add(new ArrayList<Integer>(arr));
                return;
            }
            
            Set<Integer> used = new HashSet<>();
            for(int i=pos; i<n; i++){
                if(used.contains(arr.get(i)))
                    continue;
                used.add(arr.get(i));
                
                Collections.swap(arr, pos, i);
                helper(arr, pos+1, res);
                Collections.swap(arr, pos, i);
            }
        }
    // Driver code
    public static void main(String args[])
    {
        ArrayList<Integer> arr= new ArrayList<>(Arrays.asList(3,3,8,8,9,9,9));
        for(var v:get_permutations(arr)){
            System.out.println(v);
        }
    }
}

另一种不使用swap的实现（依赖排序+相邻比较） #

如果想使用相邻元素比较的逻辑，需要改用visited数组标记已使用的元素，这样数组始终保持有序状态，相邻比较就能生效：

import java.util.*; 

public class test {
    static ArrayList<ArrayList<Integer>> get_permutations(ArrayList<Integer> arr) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Collections.sort(arr);
        boolean[] visited = new boolean[arr.size()];
        helper(arr, new ArrayList<>(), visited, res);
        return res;
    }

    static void helper(ArrayList<Integer> arr, ArrayList<Integer> path, boolean[] visited, ArrayList<ArrayList<Integer>> res) {
        if (path.size() == arr.size()) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < arr.size(); i++) {
            // 跳过已使用的元素，或者同一层递归中已经处理过的相同元素
            if (visited[i] || (i > 0 && arr.get(i).equals(arr.get(i-1)) && !visited[i-1])) {
                continue;
            }
            visited[i] = true;
            path.add(arr.get(i));
            helper(arr, path, visited, res);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }

    // Driver code
    public static void main(String args[]) {
        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(3,3,8,8,9,9,9));
        for (var v : get_permutations(arr)) {
            System.out.println(v);
        }
    }
}

这里的!visited[i-1]是关键：确保同一层递归中，只有第一个未被使用的相同元素会被处理，后续相同元素会被跳过，避免重复排列。

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