1

I am trying to get a dictionary that looks like this:

{1:{2:{3:{4:'foo'}}}}

to look like this:

'foo': [1,2,3,4]

The dictionary is nested to an unknown depth. This is definitely testing my recursion knowledge.

So far I have this. I think this works. However, I am wondering if there is a more pythonic way of doing this:

def denest(nested_dict):
    denested_dict = {}
    for k, v in nested_dict.items():
        if isinstance(v, dict):
            sub_dict = denest(v)
            for t, s in sub_dict.items():
                sub_dict[t] +=[k]
            denested_dict.update(sub_dict)
        else:
            denested_dict[v] = [k]

    return denested_dict
eljusticiero67
  • 2,257
  • 4
  • 15
  • 18
  • 2
    What if there was an additional key in one of the nested dictionaries? Do you want multiple lists linked to each path? – user3483203 Oct 12 '18 at 21:17
  • You may find my [`show_indices`](https://stackoverflow.com/a/52414034/4014959) helpful when dealing with nested data structures like this. – PM 2Ring Oct 12 '18 at 23:27

1 Answers1

4

You can keep track of the keys that have been seen:

def build_new(_d, seen = []):
  [[a, b]] = _d.items()
  return {b:seen+[a]} if not isinstance(b, dict) else build_new(b, seen+[a])

print(build_new({1:{2:{3:{4:'foo'}}}}))

Output:

{'foo': [1, 2, 3, 4]}

However, the above solution will only work when each dictionary only has one key. To find all paths generically, use yield:

def all_paths(d, seen = []):
  for a, b in d.items():
    if not isinstance(b, dict):
      yield {b:seen+[a]}
    else:
      yield from all_paths(b, seen+[a])

d = {1:{2:{3:'bar', 4:'foo', 5:{6:'stuff'}}}}
print(list(all_paths(d)))

Output:

[{'bar': [1, 2, 3]}, {'foo': [1, 2, 4]}, {'stuff': [1, 2, 5, 6]}]
Ajax1234
  • 69,937
  • 8
  • 61
  • 102
  • @eljusticiero67 Do not call these functions on more than one dict. They won't work correctly because `seen` is a mutable default argument, so it acts as a cache, which you don't want here. – PM 2Ring Oct 12 '18 at 23:17
  • I should mention that you can get around that problem by simply passing an empty list as the `seen` arg. For more info on this topic, please see https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument – PM 2Ring Oct 12 '18 at 23:36