Инвертировать вложенный словарь неизвестной глубины

Question

Я пытаюсь получить словарь, который выглядит так:

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

, чтобы выглядеть так:

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

Словарь вложен на неизвестную глубину.Это определенно проверяет мои знания рекурсии.

Пока у меня есть это.Я думаю, что это работает.Однако мне интересно, есть ли более питонский способ сделать это:

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

Answer 1

Вы можете отслеживать просмотренные ключи:

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'}}}}))

Вывод:

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

Однако вышеприведенное решение будет работать только тогда, когда в каждом словаре есть только один ключ,Чтобы найти все пути в общем, используйте 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)))

Вывод:

[{'bar': [1, 2, 3]}, {'foo': [1, 2, 4]}, {'stuff': [1, 2, 5, 6]}]