在Python中，计算字典中的唯一键/值对 [英] In Python, count unique key/value pairs in a dictionary

问题描述

我有一个字典，其中列出了值。这些值中的一些也是字典中其他键/值对中的键或值。我只想计算字典中有多少这些独特的对。

Ex。
dict = {'dog'：['milo'，'otis'，'laurel'，'hardy']，'cat'：['bob'，'joe']，蜀黍 '：[' 奥蒂斯， '月桂'， '耐寒'， '狗']， '鲍勃'：[ '猫'， '乔']， '耐寒'：[ '狗']}

我需要计算在dict中没有与另一个键/值共享的键/值对的数量。例如上面应该只算2，那些连接到狗和猫。即使小狗是狗唯一的，狗也是钥匙/值对强壮，因此这两者应该统一在一起（即仅1）。 （见下面的评论）
我试图通过用键B替换存在于另一个键（键B）的值中的键（键A），而不成功，因为我无法指定键B正确。

 用于键，dict.iteritems（）中的值：
 
用于键值在dict.iteriterms（）中：
如果键值为
 dict [keys] = dict.pop（key）
  

有更简单的方法吗？
提前感谢...

解决方案

如果我正确理解问题，您的字典是一个图表，您正在尝试查找连接的组件的集合。常规算法（使用深度或宽度优先搜索）可能无法正常工作，因为您的图形不是无向的（例如，您的边缘从bob和cat到joe，但没有从joe）。

相反，我建议使用不相交的数据结构。使用字典构建一个处理向父母的值映射并不困难。这是我以前提出的一个问题的一个实现：

  class DisjointSet：
 def __init __（self）：
 self.parent = {} 
 self.rank = {} 
 
 def find（self，element）：
如果元素不在self.parent中：＃个leader元素不在`parent` dict 
返回元素
 leader = self.find（self.parent [element]）＃递归搜索
 self.parent [element] = leader＃compress path by save leader as parent 
 return leader 
 
 def union（self，leader1，leader2）：
 rank1 = self.rank.get（leader1,0）
 rank2 = self.rank .get（leader2,0）
 
如果rank1> rank2：＃union by rank 
 self.parent [leader2] = leader1 
 elif rank2> rank1：
 self.parent [leader1] = leader2 
 else：＃rankks are equal 
 self.parent [leader2] = leader1＃favor leader1任意
 self.rank [leader1] = rank1 + 1＃increment rank 
  

这里是如何使用它来解决你的问题： p>

  djs = DisjointSet（）
 all_values = set（）
为key，my_dict.items（） ：
 all_values.add（key）
 all_values.update（values）
 for val值：
 l1 = djs.find（key）
 l2 = djs。 find（val）
如果l1！= l2：
 djs.union（l1，l2）
 
根= {djs.find（x）for all in all} 
 print（不相交集的数量是：，len（根））
  

第一个这段代码的一部分做了两件事情。首先，它构建一个集合，其中包含图中任何位置的所有唯一节点。其次，通过在有边缘的地方进行联合，将节点组合成不相交集。

第二步是从不相交建立一组根元素设置。

I have a dictionary that is made with a list of values. Some of these values are also keys or values in other key/value pairs in the dictionary. I would simply like to count how many of these unique pairs there are in the dictionary.

Ex. dict = {'dog':['milo','otis','laurel','hardy'],'cat':['bob','joe'],'milo':['otis','laurel','hardy','dog'],'bob':['cat','joe'],'hardy':['dog']}

I need to count the number of key/value pairs that do not have share a key/value with another in the dict. For example the above should count to only 2, those connected to dog and cat. Even though milo is unique to dog, dog is also in the key/value pair 'hardy' and both of these should therefore be counted together (ie, only 1). (See comments below) I have tried to go about it by replacing a key (key A) that exists in the values of another key (key B) with 'key B', without success however as I cannot specify key B correctly.

for keys, values in dict.iteritems():

    for key,value in dict.iteriterms():
            if key in values:
                dict[keys] = dict.pop(key)

Is there an easier method? Thanks in advance...

解决方案

If I understand the problem correctly, your dictionary is the adjacency map of a graph and you're trying to find the sets of connected components. The regular algorithm (using a depth- or breadth-first search) may not work correctly since your graph is not undirected (e.g. you have edges from "bob" and "cat" to "joe", but none coming out from "joe").

Instead, I suggest using a disjoint set data structure. It's not hard to build one using a dictionary to handle the mapping of values to parents. Here's an implementation I wrote for a previous question:

class DisjointSet:
    def __init__(self):
        self.parent = {}
        self.rank = {}

    def find(self, element):
        if element not in self.parent: # leader elements are not in `parent` dict
            return element
        leader = self.find(self.parent[element]) # search recursively
        self.parent[element] = leader # compress path by saving leader as parent
        return leader

    def union(self, leader1, leader2):
        rank1 = self.rank.get(leader1,0)
        rank2 = self.rank.get(leader2,0)

        if rank1 > rank2: # union by rank
            self.parent[leader2] = leader1
        elif rank2 > rank1:
            self.parent[leader1] = leader2
        else: # ranks are equal
            self.parent[leader2] = leader1 # favor leader1 arbitrarily
            self.rank[leader1] = rank1+1 # increment rank

And here's how you could use it to solve your problem:

djs = DisjointSet()
all_values = set()
for key, values in my_dict.items():
    all_values.add(key)
    all_values.update(values)
    for val in values:
        l1 = djs.find(key)
        l2 = djs.find(val)
        if l1 != l2:
            djs.union(l1, l2)

roots = {djs.find(x) for x in all_values}
print("The number of disjoint sets is:", len(roots))

The first part of this code does two things. First it builds a set with all the unique nodes found anywhere in the graph. Secondly, it combines the nodes into disjoint sets by doing a union wherever there's an edge.

The second step is to build up a set of "root" elements from the disjoint set.

这篇关于在Python中，计算字典中的唯一键/值对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！