求高效实现多列表无重复元素组合的方案（基于itertools）

需求说明 #

需要实现一个支持任意数量输入列表的函数，找出所有满足「从每个列表各取一个元素、所有元素互不重复」的组合，最终返回排序后去重的元组列表。示例如下：

l1 = [1, 2, 3]
l2 = [3, 4, 5]
unique_combinations(l1, l2) = [(2, 4), (3, 4), (1, 5), (1, 4), (2, 3), (2, 5), (1, 3), (3, 5)]

原实现的问题 #

原代码基于itertools.product生成所有笛卡尔积后再过滤，存在两大性能瓶颈：

1. 无效组合过多：当列表数量多、元素量大时，笛卡尔积的数量呈指数级增长，大部分组合因包含重复元素被过滤，浪费大量计算资源。
2. 判断与去重开销大：对每个元组生成set判断元素唯一性，再排序后存入集合去重，长元组的处理开销显著。

优化方案：回溯剪枝+提前去重 #

采用回溯法在组合构建过程中直接排除重复元素，同时预处理每个列表去重，从根源减少无效计算：

优化代码 #

def unique_combinations(*all_lists):
    # 预处理：每个列表先去重，减少不必要的迭代
    unique_lists = [list(set(lst)) for lst in all_lists]
    result = set()
    
    def backtrack(current_elements, current_comb, list_idx):
        # 遍历完所有列表，保存排序后的组合
        if list_idx == len(unique_lists):
            sorted_comb = tuple(sorted(current_comb))
            result.add(sorted_comb)
            return
        
        # 遍历当前列表的元素，只选未在当前组合中的元素
        for num in unique_lists[list_idx]:
            if num not in current_elements:
                # 更新元素集合和当前组合，继续递归
                new_elements = current_elements.copy()
                new_elements.add(num)
                backtrack(new_elements, current_comb + [num], list_idx + 1)
    
    # 初始化回溯：空元素集合、空组合、从第一个列表开始
    backtrack(set(), [], 0)
    return list(result)

优化点说明 #

1. 列表预处理：对每个输入列表去重，避免同一列表内的重复元素导致无效递归。
2. 回溯剪枝：在递归过程中，仅选择未出现在当前组合中的元素，完全跳过会产生重复元素的路径，大幅减少需要处理的组合数量。
3. 快速重复判断：用set存储当前组合的元素，判断元素是否重复的时间复杂度为O(1)，比原代码的len(set(x))高效。
4. 有序去重：最终对组合排序后存入集合，确保结果与原代码逻辑一致，无重复的无序组合。

性能对比 #

以3个各含10个元素的列表为例：

• 原代码需生成1000个笛卡尔积，再逐一过滤；
• 优化后仅生成10×9×8=720个有效组合，且每个步骤的判断开销更低，性能提升明显。

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