从字典中返回一组具有共同值的键对

Question

我如何编写一个函数，它需要一个字典并返回一个由至少具有一个公共值的键对组成的集合？示例：我有以下字典：dict = {'C': {'123'}, 'A': {'123', '456'}, 'D': {'123'}, 'B': {'789', '456'}, 'E': {'789'}}MyFunction(dict) 应该返回我：{("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")}

Answer 1

一个更有效的一次性解决方案是使用一个seendict 来跟踪到目前为止“看到”给定值的键列表：

pairs = set()

seen = {}

for key, values in d.items():

    for value in values:

        if value in seen:

            for seen_key in seen[value]:

                pairs.add(frozenset((key, seen_key)))

        seen.setdefault(value, []).append(key)

pairs 会变成：

{frozenset({'D', 'A'}), frozenset({'B', 'E'}), frozenset({'B', 'A'}), frozenset({'C', 'D'}), frozenset({'C', 'A'})}

如果需要，您可以轻松地将其转换为一组按字典顺序排序的元组：

{tuple(sorted(p)) for p in pairs}

返回：

{('A', 'C'), ('B', 'E'), ('C', 'D'), ('A', 'D'), ('A', 'B')}

Answer 2

使用itertools.combinations：

from itertools import combinations

d = {

    'C': {'123'}, 

    'A': {'123', '456'}, 

    'D': {'123'}, 

    'B': {'789', '456'}, 

    'E': {'789'}

}

def MyFunction(d):

    out = set()

    for i, j in combinations(d, 2):

        if d[j].intersection(d[i]) and (i, j) not in out and (j, i) not in out:

            out.add((i, j))

    return set(tuple(sorted(i)) for i in out)

print(MyFunction(d))

print(MyFunction(d) == {("A", "B"), ("A", "C"), ("A", "D"), ("B", "E"), ("C", "D")})

输出是：

{('A', 'D'), ('A', 'B'), ('B', 'E'), ('A', 'C'), ('C', 'D')}

True

如果您考虑('A', 'C')和('C', 'A')相同，则可以替换

return set(tuple(sorted(i)) for i in out)

只是

return out

Answer 3

defaultdict + combinations

对于蛮力解决方案，您可以反转集合字典，然后使用集合理解：

from collections import defaultdict

from itertools import combinations

d = {'C': {'123'}, 'A': {'123', '456'}, 

     'D': {'123'}, 'B': {'789', '456'}, 

     'E': {'789'}}

dd = defaultdict(set)

for k, v in d.items():

    for w in v:

        dd[w].add(k)

res = {frozenset(i) for v in dd.values() if len(v) >= 2 for i in combinations(v, 2)}

print(res)

{frozenset({'A', 'D'}), frozenset({'C', 'D'}),

 frozenset({'B', 'E'}), frozenset({'B', 'A'}),

 frozenset({'C', 'A'})}

如您所见，其中的项目res是frozenset对象，即它们不依赖于元组内的排序。frozenset是必需的，而不是set因为set不可散列。