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失败 - 这将需要额外的检查来避免。