Python - 从元组列表生成字典(树) [英] Python - Generate a dictionary(tree) from a list of tuples

问题描述

我有以下列表:-

a = [(1, 1), (2, 1), (3, 1), (4, 3), (5, 3), (6, 3), (7, 7), (8, 7), (9, 7)]

这是一个元组列表.元组中的元素的格式为 (Id, ParentId) 每当 Id == ParentId 时，它的根节点.列表可以是任意顺序的元组.

which is a list of tuples. Elements inside a tuple are of the format (Id, ParentId) Its root node whenever Id == ParentId. The list can be in any order of tuples.

我想使用上面的元组列表生成以下字典，

I want to generate the following dictionary using the above list of tuples,

output = [{
    'id': 1,
    'children': [{
        {
            'id': 3,
            'children': [{
                {
                    'id': 5
                },
                {
                    'id': 4
                },
                {
                    'id': 6
                }
            }]
        },
        {
            'id': 2
        }
    }]
}, {
    'id': 7,
    'children': [{
        {
            'id': 9
        },
        {
            'id': 8
        }
    }]
}]

即(就图表而言 - 阿福雷斯特)

ie (in terms of graphs- a forrest)

    1            7
   / \          / \
  2   3        8  9
     /|\
    4 5 6

我的最终输出应该是上面给出的字典.

My final output should be the dictionary given above.

我尝试了以下方法:-

我尝试过的解决方案如下:-

The solution which I've tried is the following:-

# set the value of nested dictionary.
def set_nested(d, path, value):
    reduce(lambda d, k: d.setdefault(k, {}), path[:-1], d)[path[-1]] = value
    return d

# returns the path of any node in list format
def return_parent(list, child):
    for tuple in list:
        id, parent_id = tuple
        if parent_id == id == child:
            return [parent_id]
        elif id == child:
            return [child] + return_parent(list, parent_id)

paths = []
temp = {}
for i in a:
    id, parent_id = i
    temp[id] = {'id': id}
    path = return_parent(a, id)[::-1]
    paths.append(path) # List of path is created

d = {}
for path in paths:
    for n, id in enumerate(path):
        set_nested(d, path[:n + 1], temp[id]) # setting the value of nested dictionary.

print d

我得到的输出是

{
    '1': {
        '3': {
            '6': {
                'id': '6'
            },
            '5': {
                'id': '5'
            },
            'id': '3',
            '4': {
                '10': {
                    'id': '10'
                },
                'id': '4'
            }
        },
        '2': {
            'id': '2'
        },
        'id': '1'
    },
    '7': {
        '9': {
            'id': '9'
        },
        '8': {
            'id': '8'
        },
        'id': '7'
    }
}

我很接近它，但无法获得确切的输出.另外，有没有更好的解决方案?

I'm close to it, but not able to get the exact output. Also, is there any better better solution?

推荐答案

这里有一个更简单的方法.(我从 Thomas 的回答中意识到节点可以按任何顺序进行编辑):Pass 1 创建节点(即，将它们添加到节点字典中)，而 Pass 2 然后创建 parent<->children 结构.

Here is a simpler approach. (Edited as I realized from Thomas answer that the nodes can be given in any order): Pass 1 creates the nodes (that is, adds them to the nodes dictionary), while Pass 2 then creates the parent<->children structure.

做出以下假设:没有循环(不清楚在这种情况下预期的输出是什么，由 Garret R 指出)、没有丢失边、没有丢失树根.

The following assumptions are made: No cycles (it is not clear what the expected output would be in such a case, pointed out by Garret R), no missing edges, no missing tree roots.

a = [(1, 1), (2, 1), (3, 1), (4, 3), (5, 3), (6, 3), (7, 7), (8, 7), (9, 7)]

# pass 1: create nodes dictionary
nodes = {}
for i in a:
    id, parent_id = i
    nodes[id] = { 'id': id }

# pass 2: create trees and parent-child relations
forest = []
for i in a:
    id, parent_id = i
    node = nodes[id]

    # either make the node a new tree or link it to its parent
    if id == parent_id:
        # start a new tree in the forest
        forest.append(node)
    else:
        # add new_node as child to parent
        parent = nodes[parent_id]
        if not 'children' in parent:
            # ensure parent has a 'children' field
            parent['children'] = []
        children = parent['children']
        children.append(node)

print forest

为什么您的解决方案没有按预期工作?

Why does your solution not work as you expected?

这里有一个关于顶级的提示:您想要获得的输出是一个树列表.但是，您正在处理的变量 (d) 需要是一个字典，因为在函数 set_nested 中，您对其应用了 setdefaults 方法.

Here's a hint regarding the top-level: The output you want to obtain is a list of trees. The variable you are dealing with (d), however, needs to be a dictionary, because in function set_nested you apply the setdefaults method to it.

这篇关于Python - 从元组列表生成字典(树)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！