Breaking nested dictionary into list

Question

I have been handling data from graph theory lately. I need to reiterate the shortest path in a form of nested dictionary to a tuple of lists.

For example:

What I received:

{0:{2:{4:{},3:{}}},1:{2:{2:{},7:{}}}}

What I want:

[[4,2,0],[3,2,0],[2,2,1],[7,2,1]]

My first thought was to define a function to append the list. However, I have been struggling from that for several hours already. I have no clue to get into the deepest keys of the dictionary…

Look forward to hearing advice from you guys, really appreciate of your help!!!

(P.s I have the number of layers of the nest, such as 3 for the above example)

I'm struggling to understand how you are getting from one to the other. I see all those same numbers in the two, but the pattern is eluding me. Can you explain the logic to get from nested dictionary to a list of lists? — JNevill, Apr 06 '22 at 19:59
@JNevill they're going from each leaf node (the deepest level) and tracing the paths to the root nodes, so since the first part of the dict is `0 -> 2 -> (4, 3)`, they get the lists `[3, 2, 0]` and `[4, 2, 0]` — Pranav Hosangadi, Apr 06 '22 at 20:00
@JNevill The process is to start from the most inner layer (the empty sub dictionary), and then get back to the outer ones, one by one — Fletcher Ng, Apr 06 '22 at 20:02
What have you tried? You should show the attempt that got you closest and ask a specific question about a problem you encountered with that. Traversing trees is covered pretty well in lots of online resources. What _specifically_ did you struggle with? — Pranav Hosangadi, Apr 06 '22 at 20:03
Are there any ways to draw out the deepest layer just by knowing the number of layers? My thought is to use for i in dictionary, and then for item in i, so on and so forth… — Fletcher Ng, Apr 06 '22 at 20:06
@PranavHosangadi I am sorry, this is the first time I ask question — Fletcher Ng, Apr 06 '22 at 20:07
You probably want to take a look at recursive functions that will drill down into a dictionary. If you encounter a dictionary that isn't empty, find the path to the leaf nodes of _that_ dictionary, and then append that list to the current path — Pranav Hosangadi, Apr 06 '22 at 20:09
@PranavHosangadi Thank you for your advice, I will start from this direction first! — Fletcher Ng, Apr 06 '22 at 20:15

Pranav Hosangadi · Accepted Answer · 2022-04-06T20:38:22.410

2

A recursive approach works for this. Define a function that will return the path to the nodes in your dictionary like so:

For each item in the dictionary
- if the item is not a dictionary, or an empty dictionary, we yield its key.
- if the item is a non-empty dictionary, we get the path to the children of this item, and append the item's key to this path before yielding.

def dict_keys_to_list(d):
    for k, v in d.items():
        if isinstance(v, dict) and v:
            for c in dict_keys_to_list(v):
                yield c + [k]
        else:
            yield [k]

To use this:

d = {0:{2:{4:{},3:{}}},1:{2:{2:{},7:{}}}}
x = list(dict_keys_to_list(d))
print(x)

gives:

[[4, 2, 0], [3, 2, 0], [2, 2, 1], [7, 2, 1]]

edited Apr 06 '22 at 20:38

answered Apr 06 '22 at 20:17

Pranav Hosangadi

23,755
7
44
70

Interestingly, Pranav and I have a different recursive approach. This one retrieves the values back up in the recursive calls to yield them, while mine pushes the values down for the last branch to yield them ;) – mozway Apr 06 '22 at 20:29
1

The order of the items in the output seems however incorrect – mozway Apr 06 '22 at 20:31
@FletcherNg here's some more information about `yield`: https://stackoverflow.com/q/231767/843953 Look up the docs for any funcions you don't know, and feel free to add a comment if you have questions. – Pranav Hosangadi Apr 06 '22 at 20:32
1

I took the liberty to fix the code ;) – mozway Apr 06 '22 at 20:35

mozway · Answer 2 · 2022-04-06T20:25:32.167

You can use a recursive generator:

def unnest(d, val=[]):
    if d == {}:
        yield val
    else:
        for k,v in d.items():
            yield from unnest(v, [k]+val)
            
list(unnest(d))

Output:

[[4, 2, 0], [3, 2, 0], [2, 2, 1], [7, 2, 1]]

How it works:

for each key, value pair, run a recursive iteration on the sub dictionaries passing the key as parameter.
at each step the new key is added on front of the list
when an empty dictionary is found the path is over, yield the list

Breaking nested dictionary into list

2 Answers2