Python：キーと値のペアのリストから任意にネストされた辞書を作成する

Question

Pythonのキーと値のペアのリストから任意にネストされた辞書を作成しようとしています。 1を達成するための入力が、目標は、巣にすべてのキーと値のペアであることを考えると

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

あなたは、2段階のプロセスでこれを行う最初の接続ノードにノードのグラフにエッジのリストに変換することができ：

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が失敗するまで再帰します。回避するには追加のチェックが必要です。