递归函数以分层嵌套平面列表

Question

我已经看到有相当多的问题或多或少地解决了这个问题，但我还没有设法将它们应用到我的特定用例中，我已经挠头尝试了几天不同的解决方案

我有一个字典列表，它们的层次结构位置编码为一个索引编号字符串——我想使用这些索引将字典重新排列成嵌套的层次结构

以下是一些示例数据：

my_data = [{'id':1, 'text':'one', 'path':'1'},
           {'id':2, 'text':'two', 'path':'3.1'},
           {'id':3, 'text':'three', 'path':'2.1.1'},
           {'id':4, 'text':'four', 'path':'3.2.1'},
           {'id':5, 'text':'five', 'path':'2.1.2'},
           {'id':6, 'text':'six', 'path':'3.2.2'},
           {'id':7, 'text':'seven', 'path':'2'},
           {'id':8, 'text':'eight', 'path':'3'},
           {'id':9, 'text':'nine', 'path':'3.2'},
           {'id':10, 'text':'ten', 'path':'2.1'}]

以下是我努力实现的目标：

result = {1:{'id':1, 'text':'one', 'path':'1'},
          2:{'id':7, 'text':'seven', 'path':'2', 'children':{
              1:{'id':10, 'text':'ten', 'path':'2.1', 'children':{
                  1:{'id':3, 'text':'three', 'path':'2.1.1'},
                  2:{'id':5, 'text':'five', 'path':'2.1.2'}
                  }}}},
          3:{'id':8, 'text':'eight', 'path':'3', 'children':{
              1:{'id':2, 'text':'two', 'path':'3.1'},
              2:{'id':9, 'text':'nine', 'path':'3.2', 'children':{
                  1:{'id':4, 'text':'four', 'path':'3.2.1'},
                  2:{'id':6, 'text':'six', 'path':'3.2.2'}
                  }}}}
          }

由于各个数据字典的路径不以任何逻辑顺序出现，因此我在整个过程中使用字典，而不是字典列表，因为这允许我在结构中创建“空”空间。我真的不想依赖于对初始列表中的词典重新排序

这是我的密码：

#%%
class my_dict(dict):
    def rec_update(self, index, dictObj): # extend the dict class with recursive update function
        """
                Parameters
        ----------
        index : list
            path to dictObj.
        dictObj : dict
            data object.

        Returns: updates the dictionary instance
        -------
        None.

        """  
        pos = index[0]
        index.pop(0)
        if len(index) != 0:
            self.update({pos : {'children' : {self.rec_update(index, dictObj)}}})
        else:
            self.update({pos : dictObj})

#%%
dataOut = my_dict() #create empty dictionary to receive result
dataOut.clear()

# dictObj = my_data[0] # for testing
# dictObj = my_data[1]

for dictObj in my_data:
    index = dictObj.get('path').split(".") # create the path list
    dataOut.rec_update(index, dictObj) # place the current data dictionary in the hierarchy

代码的问题是类定义self.rec_update(index, dictObj)中的嵌套函数调用的结果不是“children”键的值。这是因为我没有正确理解self的范围吗

我在测试期间注意到，如果我对my_data的单个元素运行dataOut.rec_update(index, dictObj)调用，例如dictObj = my_data[1]，控制台范围中的索引列表变量会被修改，这是出乎意料的，因为我认为rec_update()函数有它自己独特的范围

我想我可以看到一个更进一步的bug，其中“children”元素将被覆盖，但我还没有到那个阶段

我欢迎任何能让我走上正轨的解释

Answer 1

这里有一个解决方案，你应该能够适应你的需要。它只是一个将my_data转换为result的独立函数：

def make_tree(data):
    ###
    ### Construct path_list and path_dict
    ###

    path_dict = {}
    path_list = []

    for data in data:
        path = data['path']
        path_split = path.split('.')
        assert len(path_split) >= 1

        path_tuple = tuple(map(int, path_split))
        assert path_tuple not in path_dict
        path_dict[path_tuple] = data
        path_list.append(path_tuple)

    ###
    ### Sort path_list.  This is sorting the tuples corresponding to
    ### each path value.  Among other things, this ensues that the
    ### parent of a path appears before the path.
    ###

    path_list.sort()

    ###
    ### Construct and return the tree
    ###

    new_path_dict = {}
    tree = {}

    for path_tuple in path_list:
        data = path_dict[path_tuple]
        path_leaf = path_tuple[-1]

        new_data = data.copy()

        if len(path_tuple) == 1:
            assert path_leaf not in tree
            tree[path_leaf] = new_data
        else:
            parent_path_tuple = path_tuple[:-1]
            assert parent_path_tuple in new_path_dict
            parent = new_path_dict[parent_path_tuple]

            if 'children' not in parent:
                children = {}
                parent['children'] = children
            else:
                children = parent['children']

            assert path_leaf not in children
            children[path_leaf] = new_data

        new_path_dict[path_tuple] = new_data

    return tree

当被称为：

result = make_tree(my_data)

它给result一个值：

{1: {'id': 1, 'text': 'one', 'path': '1'},
 2: {'id': 7, 'text': 'seven', 'path': '2', 'children': {
     1: {'id': 10, 'text': 'ten', 'path': '2.1', 'children': {
         1: {'id': 3, 'text': 'three', 'path': '2.1.1'},
         2: {'id': 5, 'text': 'five', 'path': '2.1.2'}}}}},
 3: {'id': 8, 'text': 'eight', 'path': '3', 'children': {
     1: {'id': 2, 'text': 'two', 'path': '3.1'},
     2: {'id': 9, 'text': 'nine', 'path': '3.2', 'children': {
         1: {'id': 4, 'text': 'four', 'path': '3.2.1'},
         2: {'id': 6, 'text': 'six', 'path': '3.2.2'}}}}}}

请注意，Python3字典维护添加元素的顺序，因此从这个意义上讲，构建的树在每个级别都由相应的路径组件“排序”

还请注意，原始源代码列表及其包含的词典不会因此函数而改变

Answer 2

我想我已经破解了！在这个过程中我学到了很多。（我希望如此——我已经打开了至少24个so选项卡，6个doc.python.org选项卡，可能还有20个其他选项卡——所以这是一次集体努力！）

下面是一个递归函数，用于创建所需的嵌套数据：

class my_dict(dict):                                                    # new class inherits dict()
    def rec_update(self, index, dictObj): 
        pos = index[0]                                                  # store the first index position
        index.pop(0)                                                    # remove the first position from the list
        dictTemp = my_dict()                                            # will be used to pass the nested branch to the recursive function - doesn't need defined here
        if len(index) != 0:                                             # ... then we've not arrived at the leaf yet
            if not (pos in self and 'children' in self[pos]):           # ... then create a new branch
                self[pos] = {'children': {}}                            # create template
            dictTemp = my_dict(self[pos]['children'])                   # cast the dictionary as my_dict so that it has access to the rec_update() function
            self[pos]['children'] = dictTemp.rec_update(index, dictObj) # pass data on to next level, and recurse
        else:
            if (pos in self and 'children' in self[pos]):               # ... then update existing branch
                self[pos].update(dictObj)                               # add in the data alongside pre-existing children key
            else:                                                       # populate new branch with data, finally!
                self[pos] = dictObj
        return self

这是呼叫代码：

dataOut = my_dict()

for dictObj in my_data:
    index = [int(i) for i in dictObj.get('path').split(".")] # turn path string into list and iterate; convert to integers
    dataOut.rec_update(index, dictObj)

我仍然不明白为什么在调用代码-answers welcome:-）中对函数alter index中的index进行更改

但是我确实发现我不能在我的my_dict类定义中用__copy__()函数重写dict.copy()，因此dictTemp = my_dict(self[pos]['children'])而不是dictTemp = self[pos]['children'].copy()

最后一个我仍然要解决的奇怪问题是：当我将它应用到我的生产数据时，我必须运行它两次