如何在python中递归创建未知大小的嵌套字典? [英] 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.

它从层次结构顶部的一项开始，我可以使用get_items()函数获取其下方的元素.另外，如果我在对象上调用str()，它将返回对象的名称.

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.

例如:

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 ...不能保证列表中任何对象的水平.同样，也不能保证任何级别的深度.但是，深度可能不超过10.

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?

推荐答案

正如您的标题所暗示的那样，您描述的问题是递归编程的教科书示例:每个子对象都代表了较小规模的原始挑战.另外，递归程序既不关心递归深度也不关心每个级别的宽度(只要不超过Python内置的最大递归深度，即RAM溢出).因此，应用在每个子对象上调用自身的递归函数将是完美的选择.如果我们通常调用递归函数 rf ，则解决方案的核心将类似于parent.get_items()中child的 rf(child).剩下的只是将您对输出的要求拼凑在一起:您将使用字典将 str(parent)映射到其所有子级，因此(结构上)类似于 {str(父):[parent.get_items()中的子代子}} 也将成为解决方案的一部分

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

这篇关于如何在python中递归创建未知大小的嵌套字典?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！