CODEWITHSUNDEEP
pythondjangodjango-templatesdjango-views
j_syk
j_syk

Reputation: 6621

Converting a nested dictionary to a list

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!

Upvotes: 6

Views: 20954

Answers (5)

inspectorG4dget
inspectorG4dget

Reputation: 113915

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

Upvotes: 0

Lauritz V. Thaulow
Lauritz V. Thaulow

Reputation: 50995

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()):)

Upvotes: 2

Emmanuel
Emmanuel

Reputation: 14209

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

Upvotes: 0

Mihai
Mihai

Reputation: 2865

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

Upvotes: 1

C&#233;dric Julien
C&#233;dric Julien

Reputation: 80761

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)

Upvotes: 12

Related Questions