鏈接到嵌套字典的元組串列

我有一個元組串列。這可能看起來像這樣：

tuple_list = [
             ('species',  'flower'),
             ('flower', 'dorsal flower'),
             ('dorsal flower', 'pink'),
             ('pink', 'white'),
             ('pink', 'greenish'),
             ('species', 'branch'), 
    ]

注意：元組不是按順序排列的，在本例中，它們的順序也可能不同。“深度”也可以變化。

我想創建一個看起來像這樣的 dict 字典：

dod = {'species': {'branch':{},'flower': {'dorsal flower':{'pink': {'white':{}}, 'greenish':{}}}}}

在這種情況下，我希望物種處于頂層，因為它沒有“包含”物種的專案。例如物種包含“花”和“枝”等。

我覺得這整個程序可以包裝在一個簡單的遞回函式（例如yield from）中，而不是撰寫一個迭代所有值的精細 for 回圈。

最后，我想使用這個函式來創建一個串列串列，其中包含正確的值作為串列（感謝 @Stef 這個函式）：

def undict_to_lists(d, acc = []):
    if d == {}:
        yield acc
    else:
        for k, v in d.items():
            yield from undict_to_tuples(v, acc   [k,])

這將導致以下結果：

print(list(undict_to_lists(dod)))
[['species', 'branch'],
 ['species', 'flower', 'dorsal flower', 'pink', 'white'],
 ['species', 'flower', 'dorsal flower', 'greenish']]

感謝您的思考！歡迎所有建議。

uj5u.com熱心網友回復：

您可以首先為輸入中出現的每個鍵創建一個字典鍵（{}作為值）。然后迭代這些元組以找到與開始鍵對應的值，并使用結束鍵和與該結束鍵對應的子字典填充子字典。

最后，通過排除所有作為子節點的節點來匯出哪個是根。

tuple_list = [('species',  'flower'), ('flower', 'dorsal flower'), ('dorsal flower', 'pink'),('pink', 'white'),('pink', 'greenish'),('species', 'branch')]

d = { key: {} for pair in tuple_list for key in pair }
for start, end in tuple_list:
    d[start][end] = d[end]

root = None
for key in set(d.keys()).difference(end for _, end in tuple_list):
    root = d[key]

print(root)

uj5u.com熱心網友回復：

tuple_list = [
    ('species',  'flower'),
    ('flower', 'dorsal flower'),
    ('dorsal flower', 'pink'),
    ('pink', 'white'),
    ('pink', 'greenish'),
    ('species', 'branch'), 
]

# Create the nested dict,  using a "master" dict 
# to quickly look up nodes in the nested dict.
nested_dict, master_dict = {}, {}
for a, b in tuple_list:
    if a not in master_dict:
        nested_dict[a] = master_dict[a] = {}
    master_dict[a][b] = master_dict[b] = {}

# Flatten into lists.
def flatten_dict(d):
    if not d:
        return [[]]
    return [[k]   f for k, v in d.items() for f in flatten_dict(v)]

print(flatten_dict(nested_dict))
#[['species', 'flower', 'dorsal flower', 'pink', 'white'], 
# ['species', 'flower', 'dorsal flower', 'pink', 'greenish'],
# ['species', 'branch']]

uj5u.com熱心網友回復：

這是另一種選擇（大致基于@trincot 答案），它使用 adefaultdict稍微簡化代碼，并在遍歷元組串列時計算出樹的根：

from collections import defaultdict

d = defaultdict(dict)
root = tuple_list[0][0]            # first parent value
for parent, child in tuple_list:
    d[parent][child] = d[child]
    if root == child:
        root = parent


result = { root : d[root] }

輸出：

{
    "species": {
        "branch": {},
        "flower": {
            "dorsal flower": {
                "pink": {
                    "greenish": {},
                    "white": {}
                }
            }
        }
    }
}

uj5u.com熱心網友回復：

選擇 ：

def find_node( tree, parent, child ):
    if parent in tree:
        tree[parent][child] = {}
        return True

    for node in tree.values():
        if find_node( node, parent, child ):
            return True
    
    # new node
    tree[parent] = { child : {} }
    
root = {}
for parent, child in tuple_list:
    find_node( root, parent, child )

標籤：Python 字典 递归 嵌套列表

上一篇：Prolog-除法

下一篇：如何在OCaml的串列中提取元組的第n個元素