Cycling nested dictionary values

Question

I need the ability to breadth-first cycle through the deep-nested properties of a dict. This gets me part of the way there (https://stackoverflow.com/a/10756615/5932433) but the result is not what I need.

Given the following data structure:

data = {
  "a": {
    "c": 1,
    "d": 3,
  },
  "b": {
    "e": 2,
    "f": 4,
  }
}

I need a method that will return the following:

for _, v in cycle(tree_iter(data)):
  print v

# 1 (a -> c)
# 2 (b -> e)
# 3 (a -> d)
# 4 (b -> f)
# 1
# 2
# 3
# 4
# ...etc...

This is the method I have right now for tree_iter:

def tree_iter(nested):
    for key, value in nested.iteritems():
        if isinstance(value, Mapping):
            for inner_key, inner_value in tree_iter(value):
                yield inner_key, inner_value
        else:
            yield key, value

Note that order doesn't need to be guaranteed, as long as it's consistent. Each iteration should cycle through a/b, then cycle through the nested values.

Also, the structure of the dict will be consistent. All the values will be at level n. — thejohnbackes, Mar 26 '19 at 00:45

score 0 · Answer 1 · answered Mar 26 '19 at 00:46

Your current code appears to do a DFS, so you can return a list of lists from the DFS, zip them, and then flatten. Not the most elegant, but it should work.

def tree_iter_dfs(nested):
    for key, value in nested.iteritems():
        if isinstance(value, Mapping):
            yield value.items()
        else:
            yield [(key, value)]

# https://stackoverflow.com/a/952952/5309823
def flatten(l):
    return [item for sublist in l for item in sublist]

def tree_iter_bfs(nested):
    dfs = tree_iter_dfs(nested)
    return flatten(zip(*dfs))

print(list(tree_iter_bfs(data)))
# [('c', 1), ('e', 2), ('d', 3), ('f', 4)]

Change things around to iterables as necessary; I didn't know what version of Python you were using, etc.

Cycling nested dictionary values

1 Answers1