如何遍历前缀相同的多个列表并实现递归扩展去重

输入数据 #

以下是前缀均为LIST的初始列表：

LISTA = ['E', 'H']
LISTB = ['G','C']
LISTC = ['B','G','D']
LISTD = ['C']
LISTE = ['A']
LISTF = ['G']
LISTG = ['B','C','F']
LISTH = ['A']

实现逻辑 #

需要递归将每个列表元素对应的LIST列表内容合并，最终去重得到新列表：

• 以LISTB为例：初始包含G和C，需先合并LISTG、LISTC的内容；接着对新增元素（如F、D）继续递归合并其对应LIST的内容；跳过与根节点（LISTB的B）相同的元素避免循环；最后对所有内容去重得到结果。

预期输出 #

处理后各列表的结果如下（元素顺序可能因遍历逻辑略有不同，但核心元素一致）：

LISTA: ['E','H']
LISTB: ['G','C','D','F']
LISTC: ['B','G','D','F']
LISTD: ['C','B','G','F']
LISTE: ['A','H']
LISTF: ['G','B','C','D']
LISTG: ['B','C','F','D']
LISTH: ['A','E']

Python实现方案 #

# 将所有LIST存入字典，通过键快速查找对应列表
lists = {
    'A': ['E', 'H'],
    'B': ['G','C'],
    'C': ['B','G','D'],
    'D': ['C'],
    'E': ['A'],
    'F': ['G'],
    'G': ['B','C','F'],
    'H': ['A']
}

def merge_recursive(root_key, current_key, visited=None):
    # 初始化已访问集合，避免循环递归
    if visited is None:
        visited = set()
    if current_key in visited:
        return []
    visited.add(current_key)
    
    result = []
    for item in lists[current_key]:
        # 跳过与根节点相同的元素，防止循环引用
        if item == root_key:
            continue
        result.append(item)
        # 递归处理当前元素对应的列表
        result.extend(merge_recursive(root_key, item, visited.copy()))
    
    # 去重并保留元素首次出现的顺序
    unique_result = []
    seen = set()
    for elem in result:
        if elem not in seen:
            seen.add(elem)
            unique_result.append(elem)
    return unique_result

# 生成并打印所有处理后的列表
for key in sorted(lists.keys()):
    merged = merge_recursive(key, key)
    print(f"LIST{key}: {merged}")

代码说明 #

1. 字典存储：把所有LIST按键（如'A'、'B'）存入字典，方便快速查找对应元素的列表。
2. 递归遍历：使用递归函数遍历每个元素对应的列表，通过visited集合避免重复处理同一节点，同时跳过与根节点相同的元素防止循环。
3. 去重处理：遍历结果列表，只保留首次出现的元素，确保最终列表无重复且元素顺序符合遍历顺序。

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