将嵌套字典转换为列表

Question

我知道这里有很多字典可以列出问题，但我找不到适合我的情况所需的信息，所以我问一个新问题。

一些背景：我为我的模型使用分层包，生成树结构的内置函数输出一个嵌套循环来指示父母、孩子等。我的目标是将逻辑保留在视图中并输出一个列表，以便我可以简单地在我的模板中循环它。

这是我的数据，采用树结构：

1
-1.1
--1.1.1
---1.1.1.1
--1.1.2
-1.2
--1.2.1
--1.2.2
-1.3

这是我得到的嵌套字典

{
 <Part: 1.1>:
 {
   <Part: 1.1.1>:
     {
       <Part: 1.1.1.1>: {}
     }, 
   <Part: 1.1.2>: {}
 },
 <Part: 1.2>: 
 {
   <Part: 1.2.1>: {},
   <Part: 1.2.2>: {}
 }, 
 <Part: 1.3>: {}
}

，或者如果您不喜欢我尝试分解它的方式，这是我在一行中得到的内容：

{<Part: 1.1>: {<Part: 1.1.1>: {<Part: 1.1.1.1>: {}}, <Part: 1.1.2>: {}}, <Part: 1.2>: {<Part: 1.2.1>: {}, <Part: 1.2.2>: {}}, <Part: 1.3>: {}}

我的内容d 喜欢的是得到：

[<Part: 1.1>, <Part: 1.1.1>, <Part: 1.1.1.1>, <Part: 1.1.2>, <Part: 1.2>, <Part: 1.2.2>, <Part: 1.2.1>, <Part: 1.3>,]

我尝试迭代 dict.items 中的键，但随后我只得到顶级键 (1.1, 1.2, 1.3)

我需要做什么才能更深入？

谢谢！

Answer 1

我认为递归可以成为你的朋友：

top = {"<Part: 1.1>": {"<Part: 1.1.1>": {"<Part: 1.1.1.1>": {}}, "<Part: 1.1.2>": {}}, "<Part: 1.2>": {"<Part: 1.2.1>": {}, "<Part: 1.2.2>": {}}, "<Part: 1.3>": {}}

 def grab_children(father):
    local_list = []
    for key, value in father.iteritems():
        local_list.append(key)
        local_list.extend(grab_children(value))
    return local_list

print grab_children(top)

Answer 2

之前的所有解决方案都递归地构建大量列表，然后将它们扩展到越来越大的列表，直到得到最终答案。虽然它有效，但从性能角度来看它并不是最佳的，因为它创建了许多您实际上不需要的列表，并且涉及将相同的项目多次扩展到其父列表中。有些解决方案还忘记对键进行排序。

top = {"<Part: 1.1>": {"<Part: 1.1.1>": {"<Part: 1.1.1.1>": {}}, "<Part: 1.1.2>": {}}, "<Part: 1.2>": {"<Part: 1.2.1>": {}, "<Part: 1.2.2>": {}}, "<Part: 1.3>": {}}

def flatten(d, ret=None):
    if ret is None:
        ret = []
    for k, v in sorted(d.items()):
        ret.append(k)
        if v:
            flatten(v, ret)
    return ret

def test():
    flatten(top)

根据 python -m timeit -s "import flatten" "flatten.test()"，此方法每个循环使用 8.57 usecs，而 Cédrics 答案的每个循环使用 14.4 usecs，当更新为也排序时正确输出（for key, value insorted(father.items()):）

Answer 3

起始...呃，我的意思是，递归。试试这个：

def recurse(dict):
    result = []
    for key in dict:
        result.append(key)
        result.extend(recurse(dict[key]))
    return result

Answer 4

根据Mihai的回答：你需要对你的钥匙进行排序，否则你可能会遇到问题：

def recurse(d):
    result = []
    for key in sorted(d.keys()):
        result.append(key)
        result.extend(recurse(d[key]))
    return result

Answer 5

这个问题不能通过简单的字典迭代来解决。您需要一种名为 递归下降 的算法，

def getKeys(D, answer):
    if not D:
        return
    else:
        for k in D:
            answer.append(k)
            getKeys(D[k], answer)

if __name__ == "__main__":
    d = {"<Part: 1.1>": {"<Part: 1.1.1>": {"<Part: 1.1.1.1>": {}}, "<Part: 1.1.2>": {}}, "<Part: 1.2>": {"<Part: 1.2.1>": {}, "<Part: 1.2.2>": {}}, "<Part: 1.3>": {}}
    answer = []
    getKeys(d, answer)
    print answer

该算法已经过测试并且正在工作

希望这会有所帮助