CODEWITHSUNDEEP
pythondictionaryrecursion
narnia649
narnia649

Reputation: 381

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

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?

Upvotes: 0

Views: 880

Answers (1)

Lukas Thaler
Lukas Thaler

Reputation: 2720

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': {}}}

Upvotes: 2

Related Questions