Python:使用字典递归构建列表列表

Question

我有一个非常复杂的问题，我希望在这里解决：

我有一本字典：

{
"1": {
"1.1": {
"1.1.1": {}
},
"1.2": {
"1.2.1": {}
}
},
"2": {
"2.1": {
"2.1.1": {}
},
"2.2": {
"2.2.2": {}
}
}
}

其结构不会总是相同的(即在任何子字典中都可能有进一步的嵌套或更多的键(。我需要能够根据一些输入生成一个特定排序的列表列表(包含的子列表不需要排序(。列表的结构以词典为基础。考虑到字典中的所有关键字，列表列表看起来像：

[['1', '2'], ['1.2', '1.1'], ['1.1.1'], ['1.2.1'], ['2.2', '2.1'], ['2.1.1'], ['2.2.2']]

也就是说，第一个子列表包含字典最高级别的两个键。第二子列表包含在第一"；最高级别"；钥匙第三和第四子列表包含在"；第二级"；字典的。(等等(

我需要一个函数，它将根据输入(即嵌套字典中的任何键(返回正确的列表列表。例如：

function('2.2.2')
>>> [['2'], None, None, None, ['2.2'], None, ['2.2.2']] # or [['2'], [], [], [], ['2.2'], [], ['2.2.2']]
function('1.1')
>>> [['1'], ['1.1'], None, None, None, None, None] # or [['1'], ['1.1'], [], [], [], [], []]
function('1.2.1')
>>> [['1'], ['1.2'], None, ['1.2.1'], None, None, None] # or [['1'], ['1.2'], [], ['1.2.1'], None, [], []]

这几乎就像我需要能够"；知道"；字典的结构。我一直在想，如果我能在字典中找到输入键，然后追踪它，我将能够生成列表列表，但

1. 我怎样才能递归"；向上"；在字典和
2. 在世界上我如何将信息存储在列表中；去吧">

Answer 1

您的主列表只是dict结构中所有键的深度优先列表。获得这个相当容易：

def dive_into(d):
if d and isinstance(d, dict):
yield list(d.keys())
for v in d.values():
yield from dive_into(v)

d = {
"1": {
"1.1": {
"1.1.1": {}
},
"1.2": {
"1.2.1": {}
}
},
"2": {
"2.1": {
"2.1.1": {}
},
"2.2": {
"2.2.2": {}
}
}
}
master_list = list(dive_into(d))
# [['1', '2'], ['1.1', '1.2'], ['1.1.1'], ['1.2.1'], ['2.1', '2.2'], ['2.1.1'], ['2.2.2']]

接下来，function需要找到给定密钥的所有父密钥，并且只返回到给定密钥的路径中的密钥。由于密钥的格式总是<parent>.<child>.<grandchild>，因此您只需要遍历此列表，并返回key.startswith(e)为True:的任何元素e

def function(key):
lst = [[e for e in keys if key.startswith(e)] for keys in master_list]
return [item or None for item in lst]

用你的例子来测试这个：

>>> function('2.2.2')
Out: [['2'], None, None, None, ['2.2'], None, ['2.2.2']]
>>> function('1.1')
Out: [['1'], ['1.1'], None, None, None, None, None]
>>> function('1.2.1')
Out: [['1'], ['1.2'], None, ['1.2.1'], None, None, None]