如何遍历ArrayList生成无重复二元组合，有没有更优实现方案？

原代码存在的问题 #

1. 双重增强for循环遍历全量元素会生成大量重复有序对（如[A,B]和[B,A]），额外增加了去重判断的开销
2. saveList.containsAll() 是O(n)复杂度的判断，数据量稍大时性能会急剧下降
3. 用==比较字符串name是错误用法，应该用equals()方法判断字符串内容相等
4. 原代码存在语法问题，比如if判断没加括号，ArrayList的add方法返回boolean不能链式调用

最优解决方案 #

针对两两组合的场景，使用索引偏移的双层循环即可，内层循环的起始位置永远比外层循环大1，天然生成所有不重复的无序两两组合，完全不需要额外去重判断：

// 假设你的节点列表是List<Node> nodes
int size = nodes.size();
// 如果不需要存储所有组合的话，连结果集合都可以省，直接在循环里处理逻辑
List<List<Node>> result = new ArrayList<>();
for (int i = 0; i < size - 1; i++) {
    Node n1 = nodes.get(i);
    for (int j = i + 1; j < size; j++) {
        Node n2 = nodes.get(j);
        // 如果需要按name排除同名节点可以加这行，不需要就直接删除
        if (n1.getName().equals(n2.getName())) continue;
        List<Node> pair = new ArrayList<>();
        pair.add(n1);
        pair.add(n2);
        result.add(pair);
        // 这里直接执行你的process graph逻辑即可，无需判断组合是否已存在
        processGraph(pair);
    }
}

方案优势 #

• 时间复杂度直接优化到O(n²)，没有额外的存在性判断开销，数据量越大优势越明显
• 无需维护已处理的组合列表，内存开销更低，如果不需要留存所有组合的话甚至可以不用创建result集合
• 逻辑天然避免了重复组合、同元素组合的问题，代码更简洁易维护
• 如果后续需要扩展生成任意长度的元素组合，替换为回溯算法实现即可，当前场景下双层循环是性能最高的实现方式

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