python - 从键值对列表中创建任意嵌套的字典

Question

我正在尝试根据 Python 中的键值对列表创建任意嵌套的字典。键值对列表如下所示:

input_data = [{1:2}, {2:3}, {3:4}, {3:5}, {1:3}]

[我的实际输入数据要大得多，递归也多得多。]给定该输入，目标是嵌套所有键值对，以便实现:

{1: {2: {3: {4: null}, {5: null}}}, {3: {4: null, 5: null} } }

我一直在鼓捣一些递归函数，但一直没有突破。如果其他人有想法可以帮助解决此类嵌套问题，我将非常感谢他们的建议。

Answer 1

您可以分两步完成此操作，首先将边列表转换为节点到连接节点的图形:

In []:
graph = {}
for edge in inpt:
    for n1, n2 in edge.items():
        graph.setdefault(n1, []).append(n2)
graph

Out[]
{1: [2, 3], 2: [3], 3: [4, 5]}

注意:不要使用 input 作为变量名，它隐藏了 python 的内置 input()

然后创建一个递归函数来获取您正在寻找的路径就相当容易了，这是一个递归函数，它接受一个图和起始节点并返回该节点的路径:

In []:
def paths(graph, nodes):
    if not nodes:
        return None
    return {node: paths(graph, graph.get(node, [])) for node in nodes}

paths(graph, [1])

Out[]
{1: {2: {3: {4: None, 5: None}}, 3: {4: None, 5: None}}}

注意:您的预期输出不是有效的字典

或者您可以使用队列迭代地执行此操作:

In []:
def paths(graph, start):
    p = {}
    q = [(start, p, set())]
    while q:
        node, c, visited = q.pop()
        if node not in graph or node in visited:
            c[node] = None
            continue
        visited = visited | {node}
        for n in graph[node]:
            q.append((n, c.setdefault(node, {}), visited))
    return p

paths(graph, 1)

Out[]:
{1: {2: {3: {4: None, 5: None}}, 3: {4: None, 5: None}}}

注意:这需要有向非循环图，否则它将递归直到 python 失败 - 这需要额外的检查来避免。