Python实现多组有序列表间公共元素组合的高效求解

问题描述 #

我有多组列表，每组内的列表自身及组内列表间均已排序，且组内各列表无公共元素。需要从每组的每个列表中各选取一个元素，找出所有在各组间都存在的元素组合。目前使用暴力循环法效率过低，寻求高效的Python实现方案。

场景示例 #

• 组a：包含多个已排序列表，组内列表间无公共元素，最多可包含1000个列表

  a1 = [1, 3, 4, 8, 10]
  a2 = [12, 13, 15, 19, 20]
  a3 = [22, 23, 25]
  # ... 更多列表an
  

  要求必须从a1、a2、a3……an中各选一个元素

• 组b：包含多个已排序列表，组内列表间无公共元素，最多可包含1000个列表

  b1 = [4, 5, 7, 12]
  b2 = [13, 15, 17, 22]
  b3 = [23, 27, 30]
  # ... 更多列表bm
  

  要求必须从b1、b2、b3……bm中各选一个元素

• 组c及更多：最多可包含20组类似的列表组

符合要求的结果示例：[4, 13, 23]（该组合在组a和组b的合法选法中均存在）

当前尝试的低效代码 #

import itertools

a1 = [1, 3, 4, 8, 10]
a2 = [12, 13, 15, 19, 20]
a3 = [22, 23, 25]

b1 = [4, 5, 7, 12]
b2 = [13, 15, 17, 22]
b3 = [23, 27, 30]

ab = {}
ab1 = {}
ab2 = {}
ab3 = {}

f = 0
# 创建列表组
a = [a1, a2, a3]
b = [b1, b2, b3]

# 组长度不同则无解
if len(a) != len(b):
    print('there is no solution')

# 查找公共元素
for xa in a:
    ab1[f] = set.intersection(set(xa), set(b1))
    ab2[f] = set.intersection(set(xa), set(b2))
    ab3[f] = set.intersection(set(xa), set(b3))  
    ab[f] = set.union(ab1[f], ab2[f], ab3[f])
    f = f + 1        

# 检查是否存在无公共元素的情况
for f in range(len(a)):
    if not ab[f]:
        print('there is no solution because this set is empty -- there has to be one element common between groups of lists')

# 生成候选组合
solutions = list(itertools.product(*[ab1[0], ab2[1], ab3[2]]))
# 结果：[(4, 13, 23), (4, 15, 23)]            

核心思路 #

1. 按位置预处理公共元素：针对每个位置（比如第i个位置对应所有组的第i个列表），计算所有组在该位置的列表的公共元素集合，后续只需要从这些公共元素中生成组合。
2. 双指针优化交集计算：利用列表已排序的特性，用双指针法求交集，比转集合的方式更高效，尤其适合大规模数据。
3. 提前终止无效计算：如果某个位置的公共元素为空，直接判定整体无解，避免后续无用操作。

代码实现 #

import itertools

def get_common_elements_per_position(groups):
    """
    针对每个位置，计算所有组在该位置的列表的公共元素集合
    :param groups: 列表组的集合，格式为[[组1的列表1, 组1的列表2...], [组2的列表1, 组2的列表2...]]
    :return: 每个位置的公共元素列表，若某个位置无公共元素则返回空列表
    """
    position_count = len(groups[0])
    common_per_pos = []
    
    for pos in range(position_count):
        # 获取所有组当前位置的列表
        lists_at_pos = [group[pos] for group in groups]
        # 以第一个列表为初始基础，逐步求交集
        current_common = lists_at_pos[0]
        
        for lst in lists_at_pos[1:]:
            ptr1, ptr2 = 0, 0
            temp_common = []
            # 双指针求两个有序列表的交集
            while ptr1 < len(current_common) and ptr2 < len(lst):
                val1 = current_common[ptr1]
                val2 = lst[ptr2]
                if val1 == val2:
                    temp_common.append(val1)
                    ptr1 += 1
                    ptr2 += 1
                elif val1 < val2:
                    ptr1 += 1
                else:
                    ptr2 += 1
            current_common = temp_common
            if not current_common:
                break  # 无公共元素，终止当前位置计算
        
        if not current_common:
            return []  # 该位置无公共元素，整体无解
        common_per_pos.append(current_common)
    
    return common_per_pos

def find_common_combinations(groups):
    # 检查所有组的列表数量是否一致
    if len(set(len(group) for group in groups)) != 1:
        return []
    
    # 获取每个位置的公共元素
    common_per_pos = get_common_elements_per_position(groups)
    if not common_per_pos:
        return []
    
    # 生成所有合法组合（笛卡尔积）
    return list(itertools.product(*common_per_pos))

# 测试示例
a_group = [
    [1, 3, 4, 8, 10],
    [12, 13, 15, 19, 20],
    [22, 23, 25]
]
b_group = [
    [4, 5, 7, 12],
    [13, 15, 17, 22],
    [23, 27, 30]
]
all_groups = [a_group, b_group]

solutions = find_common_combinations(all_groups)
print(solutions)  # 输出: [(4, 13, 23), (4, 15, 23)]

优化效果说明 #

• 时间复杂度降低：双指针求交集的时间复杂度为O(n)（n为列表总长度），相比转集合的哈希操作，在处理大规模有序数据时效率提升明显。
• 减少无效计算：提前过滤掉每个位置的非公共元素，后续生成笛卡尔积的基数大幅减小，避免了暴力遍历所有可能组合的高开销。
• 扩展性强：支持最多20组、每组1000个列表的场景，无需修改核心逻辑。

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