如何实现多列表交集保留顺序并正确获取最后共同祖先（LCA）

给定如下字典：

di = {
    'A': [['A1', 'A1a'], ['A1', 'A1a'], ['A1', 'A1a'], ['A1', 'A1a'], ['A1', 'A1a']], 
    'B': [['A1', 'BT', 'B2', 'B2a', 'B2a1a']], 
    'G': [['A1', 'BT', 'CT0', 'CF', 'F5', 'GHIJK', 'G4', 'G21', 'G2a', 'G2a2b', 'G2a2b2b', 'G2a2b2b1a'],
          ['A1', 'BT', 'CT0', 'CF', 'F5', 'GHIJK', 'G4', 'G21', 'G2a'],
          ['A1', 'BT', 'CT0', 'CF', 'F5', 'GHIJK', 'G4', 'G21', 'G2a', 'G2a2b', 'G2a2b2a', 'G2a2b2a1a1b', 'G2a2b2a1a1b1', 'G2a2b2a1a1b1a2']]
}

需要为每个键获取对应列表的有序交集，最终结果要求如下：

intersection = {
    'A': ['A1', 'A1a'], 
    'B': ['A1', 'BT', 'B2', 'B2a', 'B2a1a'], 
    'G': ['A1', 'BT', 'CT0', 'CF', 'F5', 'GHIJK', 'G4', 'G21', 'G2a']
}

原本使用以下代码获取交集：

out = {}
for key in di:
  out[key] = set.intersection(*map(set, di[key]))

该代码能得到交集元素，但会丢失原有顺序，且无法正确识别最后共同祖先（LCA）——比如键G的结果是无序集合，导致LCA被误判为GHIJK而非正确的G2a。已知两列表交集保留顺序的方法，但不知道如何扩展到多列表场景。

核心思路是：以最短的列表为基准（交集长度不可能超过最短列表），按顺序检查每个元素是否存在于所有其他列表中，同时保留原有顺序。

具体实现代码如下：

def ordered_multilist_intersection(lists):
    if not lists:
        return []
    # 以最短列表为基准，减少遍历次数
    shortest = min(lists, key=len)
    # 转集合提升元素存在性判断效率
    list_sets = [set(lst) for lst in lists]
    # 按基准列表顺序筛选所有列表共有的元素
    result = []
    for item in shortest:
        if all(item in s for s in list_sets):
            result.append(item)
    return result

# 处理目标字典
out = {}
for key, value in di.items():
    out[key] = ordered_multilist_intersection(value)

print(out)

运行后输出结果：

{
    'A': ['A1', 'A1a'], 
    'B': ['A1', 'BT', 'B2', 'B2a', 'B2a1a'], 
    'G': ['A1', 'BT', 'CT0', 'CF', 'F5', 'GHIJK', 'G4', 'G21', 'G2a']
}

代码说明 #

1. 选最短列表为基准：交集的元素数量不可能超过最短列表的长度，以此为基准能减少不必要的遍历操作。
2. 集合快速判断：将每个列表转为集合，利用集合O(1)的查询效率，大幅提升元素存在性判断的速度。
3. 按顺序筛选：遍历基准列表的每个元素，仅保留所有列表都包含的元素，自然保留了原有的路径顺序，完美匹配LCA的识别需求。

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