Converting a nested dictionary to a list

Question

I know there are many dict to list questions on here but I can't quite find the information I need for my situation so I'm asking a new quetion.

Some background: I'm using a hierarchical package for my models and the built-in function which generates the tree structure outputs a nested loop to indicate parents, children, etc. My goal is to keep the logic in views and output a list so that I can simply loop over it in my templates.

Here is 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 I am getting 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 up, here is what I get in a single 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>: {}}

What I'd like is to get:

[<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've tried just iterating over the key in dict.items but then I only get the top level keys (1.1, 1.2, 1.3)

What do I need to do to get deeper?

thanks!

Answer 1

I think recursion can be your friend :

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

All of the previous solutions build lots of lists recursively and then extend them back into bigger and bigger lists until you have the final answer. While it works, it is not optimal from a performance perspective, since it creates lots of lists that you really don't need, and involves extending the same items many times into their parent lists. Some solutions also forget to sort on the keys.

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)

According to python -m timeit -s "import flatten" "flatten.test()", this method uses 8.57 usecs per loop, compared with 14.4 usecs per loop for Cédrics answer, when updated to also sort the output properly (for key, value in sorted(father.items()):)

Answer 3

Based on Mihai's answer: you need to sort your keys, else 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

Answer 4

This problem can't be solved by simple iteration over the dictionary. You need a type of algorithm called recursive descent

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

This has been tested and is working

Hope this helps

Answer 5

Inception... er, I mean, recursion. Try this:

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