在字典中合并键值对

Question

我有一个字典，其中包含员工-经理作为键值对：

{'a': 'b', 'b': 'd', 'c': 'd', 'd': 'f'}

我想用字典展示所有级别雇员-经理之间的关系（雇员的上司，他上司的上司，他上司的上司的上司等）。期望的输出为：

{'a': [b,d,f], 'b': [d,f], 'c': [d,f], 'd': [f] }

这是我的尝试，仅显示第一层：

for key, value in data.items():
    if (value in data.keys()):
        data[key] = [value]
        data[key].append(data[value])

我可以再写一个条件语句来添加下一级，但这并不是正确的方式。我对字典不是很熟悉，那么有更好的方法吗？

- user415663

---

我对字典不是很熟悉，那么有更好的方法吗？- 数据库 - kylieCatt

我不确定是否有任何Python函数可用于此目的，但我会使用拓扑排序来实现这个功能。 - Quazi Marufur Rahman

请参阅 https://en.wikipedia.org/wiki/Disjoint-set_data_structure。 - OozeMeister

另外，https://en.wikipedia.org/wiki/Transitive_closure#Algorithms - mindriot

不是一个重复的问题https://dev59.com/43VD5IYBdhLWcg3wQJOT - Frames Catherine White

Answer 1

>>> D = {'a': 'b', 'b': 'd', 'c': 'd', 'd': 'f'}
>>> res = {}
>>> for k in D:
...     res[k] = [j] = [D[k]]
...     while j in D:
...         j = D[j]
...         res[k].append(j)
... 
>>> res
{'b': ['d', 'f'], 'c': ['d', 'f'], 'd': ['f'], 'a': ['b', 'd', 'f']}

- John La Rooy

---

我应该说这是一个考虑周到、细节入微的答案。感谢您提供这样的答案，加一。 - The6thSense

什么是 [j] 语法和 "while j in D"？看起来我是新手。 - Czarek Tomczak

@CzarekTomczak，“j”用于从一个键遍历到下一个键。“[j] = [D[k]]”只是“j = D[k]”，但我将其包装在列表中，以便可以在同一行中将其分配给“res[k]”。 - John La Rooy

Answer 2

您可以将递归的概念用作：

def get_linked_list(element, hierarchy, lst):
    if element:
        lst.append(element)
        return get_linked_list(hierarchy.get(element, ""), hierarchy, lst)
    else:
        return lst

然后按照以下方式访问层次结构：

>>> d = {'a': 'b', 'b': 'd', 'c': 'd', 'd': 'f'}   
>>> print {elem:get_linked_list(elem, d, [])[1:] for elem in d.keys()}
>>> {'a': ['b', 'd', 'f'], 'c': ['d', 'f'], 'b': ['d', 'f'], 'd': ['f']}

然而，需要注意的是，如果字典中有一个项为"a": "a"，则可能会进入无限循环。

- ZdaR

Answer 3

x={'a': 'b', 'b': 'd', 'c': 'd', 'd': 'f'}
d={}
l=x.keys()
for i in l:
    d.setdefault(i,[])
    d[i].append(x[i])
    for j in l[l.index(i)+1:]:
        if j==d[i][-1]:
            d[i].append(x[j])

打印 d

输出：{'a': ['b', 'd', 'f'], 'c': ['d', 'f'], 'b': ['d', 'f'], 'd': ['f']}

- vks