python - 合并字典中具有公共(public)元素的列表

Question

如果值(列表)至少共享一个元素，我想合并字典的键和值。

输入为:

dico = {"a" : [1,2,3], "b":[9,2,89], "c":[3,12,530],"d":[34,42],"e":[34,6]}

我希望结果是这样的:

{"a,b,c" : [1,2,3,9,89,12,530], "d,e": [34,42,6] }

我尝试过的方法都不起作用...您认为这可能吗？

Answer 1

您可以使用Union-Find aka Disjoin Set方法。首先，您需要两个函数:union 和 find。我通常把它们放在某个地方以备不时之需。

def find(x):
    l = leaders[x]
    if l is not None:
        l = find(l)
        leaders[x] = l
        return l
    return x

def union(x, y):
    lx, ly = find(x), find(y)
    if lx != ly:
        leaders[lx] = ly

现在，您可以使用它们来为列表中的每个元素确定一个“领导者”...

dico = {"a" : [1,2,3], "b":[9,2,89], "c":[3,12,530],"d":[34,42],"e":[34,6]}
leaders = collections.defaultdict(lambda: None)

for val in dico.values():
    for other in val[1:]:
        union(val[0], other)        

...然后将具有相同“领导者”的元素分组。

groups = collections.defaultdict(set)
for x in leaders:
    groups[find(x)].add(x)

现在，还按第一个元素的领导者对键进行分组:

keys = collections.defaultdict(list)
for key in dico:
    keys[find(dico[key][0])].append(key)

最后组装结果。

result = {','.join(ks): groups[leader] for (leader, ks) in keys.items()}
# {'d,e': {42, 34, 6}, 'c,a,b': {1, 2, 3, 9, 12, 530, 89}}

请注意，这是使用集合，而不是列表。如果您需要保留原始顺序，只需将键分组，然后将它们各自的列表放在一起即可。