Merging Key-Value Pairings in Dictionary

Question

I have a dictionary that consists of employee-manager as key-value pairs:

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

I want to show the relations between employee-manager at all levels (employee's boss, his boss's boss, his boss's boss's boss etc.) using a dictionary. The desired output is:

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

Here is my attempt which only shows the first level:

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

I can do another conditional statement to add the next level but this would be the wrong way to go about it. I'm not very familiar with dictionaries so what would be a better approach?

__I'm not very familiar with dictionaries so what would be a better approach?__ - A Database — kylieCatt, Feb 25 '16 at 06:14
I am not sure if any python function is available for this purpose, but I would use **topological sorting** to implement this functionality. — Quazi Marufur Rahman, Feb 25 '16 at 06:19
See also https://en.wikipedia.org/wiki/Disjoint-set_data_structure — OozeMeister, Feb 25 '16 at 06:22
Also, https://en.wikipedia.org/wiki/Transitive_closure#Algorithms — mindriot, Feb 25 '16 at 10:22
Not a duplicate of http://stackoverflow.com/questions/38987/how-can-i-merge-two-python-dictionaries-in-a-single-expression — Frames Catherine White, Feb 25 '16 at 15:20

John La Rooy · Answer 1 · 2016-02-25T06:26:19.173

11

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

edited Feb 25 '16 at 06:26

answered Feb 25 '16 at 06:20

John La Rooy

295,403
53
369
502

I should say this is a well thought answer with minute details. Thanks for such an answer +1. – The6thSense Feb 25 '16 at 06:47
What is the [j] syntax and "while j in D"? Looks like I'm newbie. – Czarek Tomczak Feb 29 '16 at 08:29
@CzarekTomczak, `j` is used to traverse from one key to the next. `[j] = [D[k]]` is just `j = D[k]` but I wrapped it in a list so that I could also assign it to `res[k]` in the same line. – John La Rooy Feb 29 '16 at 09:25

ZdaR · Answer 2 · 2016-02-25T06:48:05.287

You may use the concept of recursion as :

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

And then access the hierarchy as:

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

However care must be taken as this may get to an infinite loop if we have an item in the dictionary as "a": "a"

score 1 · Answer 3 · answered Feb 25 '16 at 08:05

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])

print d

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

Merging Key-Value Pairings in Dictionary

3 Answers3