如何高效优化带条件的列表笛卡尔积配对生成代码？

我需要高效生成两个元素唯一列表的笛卡尔积配对，需满足以下条件：

• 排除x == y的配对；
• 配对(x,y)和(y,x)仅保留其一。
  现有Python代码可实现需求，但循环部分效率较低，恳请提供改进建议。

原代码 #

from itertools import product
from pprint import pprint as pp

def pairs(list1, list2):
    """ Return all combinations (x,y) from list1 and list2 except:
          1. Omit combinations (x,y) where x==y """
    tuples = filter(lambda t: t[0] != t[1], product(list1,list2))

    """   2. Include only one of the combinations (x,y) and (y,x) """
    result = []
    for t in tuples:
        if not (t[1], t[0]) in result:
            result.append(t)
    return result

list1 = ['A', 'B', 'C']
list2 = ['A', 'D', 'E']
pp(pairs(list1, list1))  # 测试同一列表的情况
pp(pairs(list1, list2))  # 测试有部分公共元素的两个列表

原输出 #

[('A', 'B'), ('A', 'C'), ('B', 'C')]
[('A', 'D'),
 ('A', 'E'),
 ('B', 'A'),
 ('B', 'D'),
 ('B', 'E'),
 ('C', 'A'),
 ('C', 'D'),
 ('C', 'E')]

原代码的核心问题 #

原循环中if not (t[1], t[0]) in result这一步，每次检查都要遍历整个result列表，属于线性时间复杂度(O(n))。当列表元素数量较多时，会导致代码运行速度急剧下降。

优化方案 #

1. 用集合记录已处理的配对（通用优化）

把重复检查逻辑从列表线性查找改成集合哈希查找（时间复杂度O(1)），通过给配对生成唯一标识（比如排序后的元组）来避免(x,y)和(y,x)重复：

from itertools import product
from pprint import pprint as pp

def pairs(list1, list2):
    seen = set()
    result = []
    for x, y in product(list1, list2):
        if x == y:
            continue
        # 生成唯一键，确保(x,y)和(y,x)对应同一个标识
        unique_key = tuple(sorted((x, y)))
        if unique_key not in seen:
            seen.add(unique_key)
            result.append((x, y))
    return result

list1 = ['A', 'B', 'C']
list2 = ['A', 'D', 'E']
pp(pairs(list1, list1))
pp(pairs(list1, list2))

该方案直接解决原循环的效率瓶颈，无论输入列表是否相同都适用。

2. 针对同一列表的特殊优化

如果是生成同一列表内的配对，可以直接用itertools.combinations——它本身就生成无序的不重复配对，且自动排除x==y的情况，比笛卡尔积再过滤高效得多：

from itertools import combinations, product
from pprint import pprint as pp

def pairs(list1, list2):
    # 判断是否为同一列表（若需判断内容相同，可改为list1 == list2）
    if list1 is list2:
        return list(combinations(list1, 2))
    
    seen = set()
    result = []
    for x, y in product(list1, list2):
        if x == y:
            continue
        unique_key = tuple(sorted((x, y)))
        if unique_key not in seen:
            seen.add(unique_key)
            result.append((x, y))
    return result

3. 生成器版本（节省内存）

如果处理的列表元素数量极大，不需要一次性存储所有结果，可以改成生成器，每次只生成一个配对，大幅降低内存占用：

from itertools import product
from pprint import pprint as pp

def pairs(list1, list2):
    seen = set()
    for x, y in product(list1, list2):
        if x == y:
            continue
        unique_key = tuple(sorted((x, y)))
        if unique_key not in seen:
            seen.add(unique_key)
            yield (x, y)

list1 = ['A', 'B', 'C']
list2 = ['A', 'D', 'E']
# 生成器需要转为列表才能打印
pp(list(pairs(list1, list1)))
pp(list(pairs(list1, list2)))

优化效果对比 #

• 原代码循环部分：当结果列表有n个元素时，每次检查需要O(n)时间，总时间复杂度O(n²)；
• 优化后：每次检查仅需O(1)时间，总时间复杂度O(m)（m为笛卡尔积的元素数量），元素越多，效率提升越明显。

内容的提问来源于stack exchange，提问作者C. Pappy