How to recursively create a nested dictionary of unknown size in python?

Question

I have an object that has an unknown depth and width at every depth. Sort of like a path but it's a different type of object.

My goal is to create a nested dictionary that represents this structure.

It starts as one item at the top of the hierarchy and I can grab the elements below it using a get_items() function. Also, if I call str() on the object it returns the name of the object.

For example:

str(object) = 'top hierarchy'
object.get_items() returns a list ~ [object_level1_part1, object_level1_part2]

str(object_level1_part1) = 'level1_part1'
object_level1_part1.get_items() returns a list ~  [object_level2_part1]

str(object_level2_part2) = 'level2_part1'

etc... There is no guarantee at any level how any objects in the list there will be. Also, there is no guarantee how deep any level might go. However, there is probably nothing greater than a depth of 10.

I want to take this object & recursively search it in order to create a dictionary that would look like something below:

result_dict = {'top_hierarchy':{'level1_part1':{'level2_part1':{}}, 'level1_part2':{}}}

One of the challenges I am having is to continually add to the dictionary in a nested fashion I have to specify previous keys.

result_dict['top_hierarchy']['level1_part1']['level2_part1'] = {'level3_part1':{}}

Is there a way to create a nested dictionary recursively with unknown depth and width?

Lukas Thaler · Accepted Answer · 2021-02-16 07:59:03Z

2

As your title already suggests, the problem you describe is a textbook example for recursive programming: each child object represents the original challenge on a smaller scale. Also, a recursive program doesn't care about the recursion depth nor the width of each level (as long as the maximum recursion depth built into Python isn't exceeded or your RAM overflows, that is). Therefore, applying a recursive function that calls itself on each child object is going to be the perfect fit. If we generically call the recursive function rf, the core of the solution will look something like rf(child) for child in parent.get_items(). The rest is just piecing together the requirements you have for the output: you'll be using a dictionary mapping str(parent) to all its children, so something (structurally) similar to {str(parent): [child for child in parent.get_items()]} will also be part of the solution

With all that in mind, the solution to your problem becomes as simple as

def unpack(obj):
    return {str(o): unpack(o) for o in obj.get_items()}

result_dict = {str(object): unpack(object)}

Quick test with a class specifically thrown together to emulate your data structure:

class myObj:
    def __init__(self, name, objects=[]):
        self.name = name
        self.objects = objects
    
    def __str__(self):
        return self.name
    
    def get_items(self):
        return self.objects

# build recursive structure bottom up
l2p1 = myObj('l2p1')

l1p1 = myObj('l1p1', [l2p1])
l1p2 = myObj('l1p2')

th = myObj('th', [l1p1, l1p2])

# test the unpacking
result_dict = {str(th): unpack(th)}

result_dict
{'th': {'l1p1': {'l2p1': {}}, 'l1p2': {}}}

edited Feb 16, 2021 at 7:59

answered Feb 16, 2021 at 7:41

Lukas Thaler

2,7205 gold badges19 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

narnia649 Over a year ago

Yes, this is exactly what I was looking for. Is there a way to add additional variables to the dictionary? I tried doing the following but get an error: """ def unpack(obj): return {{str(o): unpack(o), 'values':o.get_Values()} for o in obj.get_EventFrames()} """

Lukas Thaler Over a year ago

That would require you to change the structure up a bit: you'll need a dedicated entry to collect the structure, say children: unpack(o) and a place to store the values, say values: o.get_values(). On a side note, unless your get-functions implement some calculation logic, there is no reason not to directly access the values using something like o.values. Getters and setters are unpythonic

narnia649 Over a year ago

I've been trying to implement the use of the values for the past hour, but to no avail. Would you be able to clarify how I would predefine the structure?

Lukas Thaler Over a year ago

Something along the lines of {str(o): {'children': unpack(o), 'values': o.values} for o in obj.get_items()} should hopefully work out

Collectives™ on Stack Overflow

How to recursively create a nested dictionary of unknown size in python?

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related