如何修改Java分组代码去除ArrayList重复分组并精简输出

你的问题核心在于当前的递归算法会生成分组集合顺序不同但实质相同的结果（比如[[Person1,Person2], [Person3,Person4]]和[[Person3,Person4], [Person1,Person2]]被当成了两个不同的分组方案），同时如果每组内的顺序允许互换的话，也可能产生额外重复（不过看你的代码，每组是按原数组切片生成的，暂时先聚焦分组集合的重复问题）。

方案一：事后去重（简单易实现） #

我们可以利用Set的唯一性特性，先将每个分组方案转换成一个有序的、可哈希的结构，再判断是否已经存在，避免重复加入x。具体步骤如下：

1. 为每个分组方案生成一个“唯一标识”：将foo中的每个小组排序，再把整个foo转换成一个不可变的结构（比如List<List<String>>），这样顺序不同但内容相同的分组方案会生成相同的标识。
2. 用一个Set来存储已经添加过的标识，只有当标识不在Set中时，才将foo加入x。

修改后的完整代码如下：

import java.io.IOException;
import java.util.*;

public class createGroups {
    public static ArrayList<ArrayList<String[]>> x = new ArrayList<>();
    // 用于存储已存在的分组方案的唯一标识
    private static Set<List<List<String>>> seen = new HashSet<>();

    public static void main(String[] args){
        String[] names = {"Person1", "Person2", "Person3", "Person4"};
        try {
            combination(names, 0, 2);
            printPairs();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static void combination(String[] data, int offset, int group_size) throws IOException {
        if(offset >= data.length) {
            ArrayList<String[]> foo = new ArrayList<>();
            for(int i = 0; i < data.length / group_size; i++) {
                foo.add(Arrays.copyOfRange(data, 2 * i, 2 * (i + 1)));
            }

            // 生成唯一标识：将每个小组排序，再转成不可变的List
            List<List<String>> key = new ArrayList<>();
            for (String[] group : foo) {
                List<String> sortedGroup = Arrays.asList(group.clone());
                Collections.sort(sortedGroup);
                key.add(Collections.unmodifiableList(sortedGroup));
            }
            // 对整个分组方案的顺序也排序，确保不同顺序的同一方案得到相同key
            Collections.sort(key, (a, b) -> a.get(0).compareTo(b.get(0)));

            if (!seen.contains(key)) {
                seen.add(key);
                x.add(foo);
            }
            return;
        }

        for(int i = offset; i < data.length; i++){
            for(int j = i + 1; j < data.length; j++){
                swap(data, offset, i);
                swap(data, offset + 1, j);
                combination(data, offset + group_size, group_size);
                swap(data, offset + 1, j);
                swap(data, offset, i);
            }
        }
    }

    // 以下printPairs和swap方法保持不变
    public static void printPairs(){
        for(ArrayList<String[]> q : x){
            for(String[] s : q){
                System.out.println(Arrays.toString(s));
            }
            System.out.println("\n");
        }
    }

    private static void swap(String[] data, int a, int b){
        String t = data[a];
        data[a] = data[b];
        data[b] = t;
    }
}

方案二：从递归逻辑避免重复（更高效） #

如果想从根源上不生成重复的分组，可以通过限制分组的选择顺序来实现：比如，确保每个新分组的第一个元素的“顺序”比前一个分组的第一个元素大（按字符串排序），这样就不会生成不同顺序的同一方案。

修改后的combination方法核心逻辑如下：

static void combination(String[] data, int offset, int group_size) throws IOException {
    if(offset >= data.length) {
        ArrayList<String[]> foo = new ArrayList<>();
        for(int i = 0; i < data.length / group_size; i++) {
            foo.add(Arrays.copyOfRange(data, 2 * i, 2 * (i + 1)));
        }
        x.add(foo);
        return;
    }

    // 当offset > 0时，确保当前分组的第一个元素比前一个分组的第一个元素大
    int start = offset;
    if (offset > 0) {
        String prevFirst = data[offset - group_size];
        // 找到第一个比prevFirst大的元素作为起始点
        while (start < data.length && data[start].compareTo(prevFirst) <= 0) {
            start++;
        }
    }

    for(int i = start; i < data.length; i++){
        for(int j = i + 1; j < data.length; j++){
            swap(data, offset, i);
            swap(data, offset + 1, j);
            combination(data, offset + group_size, group_size);
            swap(data, offset + 1, j);
            swap(data, offset, i);
        }
    }
}

这个改动通过限制递归的起始点，从一开始就避免生成分组顺序互换的重复方案，不需要事后去重，效率更高。

效果验证 #

对于你的测试数据{"Person1", "Person2", "Person3", "Person4"}，修改后只会生成1种唯一的分组方案：

[Person1, Person2]
[Person3, Person4]

如果你的名字列表更长（比如6个人），也只会生成所有不重复的两两分组组合。

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