我需要一个 python 函数来深入搜索列表列表的字典

Question

我有这个数据结构，一个由列表列表（一种树结构）组成的字典，其中字母是短语：

dict = {
   'A': [ ['A1', ['A2'], ['A3', ['A4'], ['A5'] ] ],
   'B': [ ['B1', ['B2'] ],
   'C': [ ['C1', ['C2', ['C3'] ], ['C4'] ] ]
}

我需要的是 returns 'list of list of elements from a root to a leaf'.

的功能

换句话说，我需要沿着每条路径探索整个树，连接重建对话的短语。

这个树结构是通过爬取 Reddit 构建的，所以每条路径都是一系列答案，所以是一个对话。

对于键 'B'，有 1 个可能的序列：['B1'、'B2']（字典键不相关）。

对于键 'A'，有 3 个可能的序列：['A1'、'A2']、['A1'、'A3'、'A4' ], ['A1', 'A3', 'A5']

对于键 'C'，有 2 个可能的序列：['C1'、'C2'、'C3']、['C1'、'C4' ]

这个问题很难形式化，我希望这些序列是正确的:)

所以，我期望的是这个输出，一个以短语列表的形式包含树中所有可能序列的列表：

[
   ['A1', 'A2'],
   ['A1', 'A3', 'A4'],
   ['A1', 'A3', 'A5'],
   ['B1', 'B2'],
   ['C1', 'C2', 'C3'],
   ['C1', 'C4']
]

我不需要结果列表中的任何特定顺序，我只需要序列。

非常感谢，我们将不胜感激！

Answer 1

这是您问题的解决方案。

首先，我们创建一个函数，将您拥有的列表转换为字典结构：

def convert_to_dict(conversation_list):
    dict_ = {}
    for sublist in conversation_list:
        dict_[sublist[0]] = convert_to_dict(sublist[1:])
    return dict_

print(convert_to_dict([['A1', ['A2'], ['A3', ['A4'], ['A5']]]]))
# {'A1': {'A2': {}, 'A3': {'A4': {}, 'A5': {}}}}

然后我们创建一个函数来获取这个字典和returns其中的对话：

def conversations(rv, lst, conversation_dict):
    for key, value in conversation_dict.items():
        if value != {}:
            rv = conversations(rv, lst + [key], value)
        else:
            rv.append(lst + [key])
    return rv

print(conversations([], [], {'A1': {'A2': {}, 'A3': {'A4': {}, 'A5': {}}}}))
# [['A1', 'A2'], ['A1', 'A3', 'A4'], ['A1', 'A3', 'A5']]

然后我们可以将两者结合在一个函数中，该函数接受您的口述和 returns 所有对话：

def get_conversations(dict):
    rv = []
    for _, value in dict.items():
        dict_ = convert_to_dict(value)
        rv += conversations([], [], dict_)
    return rv

dict_ = {
   'A': [ ['A1', ['A2'], ['A3', ['A4'], ['A5'] ] ] ],
   'B': [ ['B1', ['B2'] ] ],
   'C': [ ['C1', ['C2', ['C3'] ], ['C4'] ] ]
}
print(get_conversations(dict_))
#[['A1', 'A2'], ['A1', 'A3', 'A4'], ['A1', 'A3', 'A5'], ['B1', 'B2'], ['C1', 'C2', 'C3'], ['C1', 'C4']]

Answer 2

您可以使用递归生成器函数来获得更短的解决方案：

d = {'A': [['A1', ['A2'], ['A3', ['A4'], ['A5']]]], 'B': [['B1', ['B2']]], 'C': [['C1', ['C2', ['C3']], ['C4']]]}
def get_paths(t):
    a, *b = t
    if not b:
       yield a
    yield from [[a, *(i if isinstance(i, list) else [i])] for j in b for i in get_paths(j)]

r = [i for [a] in d.values() for i in get_paths(a)]

输出：

[['A1', 'A2'], 
 ['A1', 'A3', 'A4'], 
 ['A1', 'A3', 'A5'], 
 ['B1', 'B2'], 
 ['C1', 'C2', 'C3'], 
 ['C1', 'C4']]

我需要一个 python 函数来深入搜索列表列表的字典

I need a python function to depth first search into a dict of lists of lists

python

search

dictionary

list

depth