Geek Answers Handbook

Convert nested dictionary to list

I know that there are many questions, but I can’t find the information I need for my situation, so I ask a new question.

Some suggestion: I use a hierarchical package for my models and a built-in function that generates a tree structure, outputs a nested loop to indicate parents, children, etc. My goal is to preserve the logic in the views and outputs of the list so that I can simply iterate over it in my templates.

Here are my data in the tree structure:

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

Here is the nested dictionary that I get as a result

{
 <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>: {}
}

or if you don’t like the way I tried to break it, here is what I get in one line:

{<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>: {}}

I want to receive:

[<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>,]

I tried just iterating over the key in the dict.items file, but then I get only the top-level keys (1.1, 1.2, 1.3)

, ?

!

+5
5

, :

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)
+10

, , . , , , , , . .

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 , 14.4 usecs Cédrics, , (for key, value in sorted(father.items()):)

+2

First ... uh, I mean recursion. Try the following:

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

This problem cannot be solved by simple dictionary iteration. You need a recursive descent algorithm

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

It has been tested and works.

Hope this helps

0
source

Based on Mihai's answer: you need to sort the keys, otherwise you will probably have problems:

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

More articles:


All Articles