Fletcher Ng
Fletcher Ng

Reputation: 3

Breaking nested dictionary into list

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)

Upvotes: 0

Views: 68

Answers (2)

pho
pho

Reputation: 25489

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

  1. 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]]

Upvotes: 2

mozway
mozway

Reputation: 260455

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

Upvotes: 1

Related Questions