时间戳

首页 > 解决方案 > 分层嵌套平面列表的递归函数

python - 分层嵌套平面列表的递归函数

问题描述

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

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

以下是一些示例数据：

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正确理解范围吗？

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

我想我可以看到另一个错误，其中“孩子”元素将被覆盖，但我还没有到那个阶段。

我欢迎任何可以让我走上正轨的解释。

标签： python

解决方案

这是一个您应该能够适应您的需求的解决方案。它只是一个独立的函数，可以转换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'}}}}}}

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

另请注意，此函数不会更改原始源列表及其包含的字典。

推荐阅读