CODEWITHSUNDEEP
pythonpython-2.7listdictionarytree
Tony Ennis
Tony Ennis

Reputation: 12299

Convert a dict that simulates a tree into lists

I have a dict like this:

{
1: {
   3: {
      1: {c:32},
      2: {c:12}
      },
   4: {c: 66}
   },
2: {
   3: {c: 1},
   5: {c: 2}
   }
}

How can I elegantly unroll this tree to get:

[
[1, 3, 1, 32],
[1, 3, 2, 12],
[1, 4, 66],
[2, 3, 1],
[2, 5, 2]
]

This structure can be arbitrarily deep.

EDIT - I don't care about the order of the output. 'c' is a count of the times a particular sequence of integer was seen. So in this case, [1, 3, 1] was seen 32 times.

The exact format isn't so important, it's the technique I am after.

Upvotes: 3

Views: 180

Answers (2)

wim
wim

Reputation: 363083

Recursion:

def flatten(d, prefix=()):
    for k,v in d.items():
        if isinstance(v, dict):
            yield from flatten(v, prefix=prefix+(k,))
        else:
            yield list(prefix + (v,))

Iteration:

from collections import deque

def flatten(d):
    queue = deque([[[], d]])
    while queue:
        prefix, node = queue.popleft()
        if isinstance(node, dict):
            queue.extend([(prefix + [k], v) for k, v in node.items()])
        else:
            yield prefix[:-1] + [node]

Note: It's relatively easy to blow the stack using recursion in Python. If your data is huge, i.e. deeper than sys.getrecursionlimit(), then you should prefer the breadth-first solution - this may consume a lot of memory but it will not stack overflow.

Upvotes: 6

Patrick Haugh
Patrick Haugh

Reputation: 61032

def unroll(d):
    for k, v in d.items():
        if isinstance(v, dict):
            for l in unroll(v):
                yield [k] + l
        else:
                yield [v]

You'd call it like

list(unroll(d))

For your input I got

[[1, 3, 1, 32], [1, 3, 2, 12], [1, 4, 66], [2, 3, 1], [2, 5, 2]]

Upvotes: 4

Related Questions