在字典中合并具有公共元素的列表

Question

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

输入将是：

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

我希望外面是这样的：

^{pr2}$

我所做的一切都没用。。。你认为这有可能吗？在

Answer 1

你可以使用Union-Find aka Disjoin Set方法。首先，需要两个函数：union和{}。我通常把它们放在某处以备需要。在

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

现在，您可以使用这些来为列表中的每个元素确定一个“leader”。。。在

^{pr2}$

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

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}}

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