Python中两个列表元素的终极映射处理（含权重匹配需求）

我有两个列表a和b，b的部分元素同时存在于a中。需要创建映射关系，将a的每个元素对应到b中的「终极」元素（例如a中的元素x对应b中的y，若y也在a中且对应b中的z，则x需对应z）。当存在多个「终极」匹配时，需借助第三个列表c进行权重计算。

示例输入：

a = [1, 2, 3, 4, 5, 1, 2]
b = [6, 1, 7, 1, 8, 9, 3]
c = [.5, .3, 1, 1, 1, .5, .7]

理想输出：

result = {1: [6, 9], 2: [6, 9, 7], 3: [7], 4: [6, 9], 5: [8]}
weights = {1: [.5, .5], 2: [.15, .15, .7], 3: [1], 4: [.5, .5], 5: [1]} 

我尝试用while循环解决，但该方案无法处理多匹配场景及权重计算：

both = set(a).intersection(set(b))
mydict = dict(zip(a, b))
result = {x: mydict[v] if v in mydict.keys() else v for k, v in mydict.items()}

while set(result.values()).issubset(both)==False:
   result = {x: mydict[v] if v in mydict.keys() else v for k, v in mydict.items()}

请问该如何改进？

要处理多匹配和权重传递，需先构建带权重的映射链，再通过递归追踪每个元素的终极节点并累积权重，具体步骤如下：

1. 构建初始多值映射（保留所有匹配及权重） #

普通字典会覆盖重复键的匹配，因此用defaultdict为每个a元素存储所有对应的b元素及权重：

from collections import defaultdict

# 初始化映射：key为a的元素，value为[(b元素, 对应权重)]的列表
initial_map = defaultdict(list)
for ai, bi, ci in zip(a, b, c):
    initial_map[ai].append((bi, ci))

2. 递归追踪终极节点并计算累积权重 #

编写递归函数，为每个元素找到所有无法继续映射到a中元素的终极节点，同时计算路径上的权重乘积：

def get_final_nodes(node, visited=None):
    # 用visited集合避免循环映射导致无限递归
    if visited is None:
        visited = set()
    if node in visited:
        return []
    visited.add(node)
    
    # 当前节点不在初始映射中，即为终极节点
    if node not in initial_map:
        visited.remove(node)
        return [(node, 1.0)]
    
    final_pairs = []
    for next_node, weight in initial_map[node]:
        # 递归获取下一级的终极节点，乘上当前权重
        for final_node, sub_weight in get_final_nodes(next_node, visited):
            final_pairs.append((final_node, weight * sub_weight))
    visited.remove(node)
    return final_pairs

3. 生成结果与权重字典 #

遍历a的所有唯一元素，调用上述函数整理出最终的映射结果和权重列表：

unique_a = set(a)
result = {}
weights = {}

for node in unique_a:
    final_pairs = get_final_nodes(node)
    # 拆分节点和权重到各自字典
    result[node] = [pair[0] for pair in final_pairs]
    weights[node] = [pair[1] for pair in final_pairs]

4. 验证输出 #

运行代码后，得到的结果与示例完全一致：

print(result)
# {1: [6, 9], 2: [6, 9, 7], 3: [7], 4: [6, 9], 5: [8]}
print(weights)
# {1: [0.5, 0.5], 2: [0.15, 0.15, 0.7], 3: [1.0], 4: [0.5, 0.5], 5: [1.0]}

核心改进点 #

• 替换普通字典为defaultdict，保留每个a元素的所有匹配项及对应权重
• 递归处理多层映射关系，自动计算路径上的权重乘积
• 加入循环检测机制，避免因循环映射导致的程序崩溃

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