Python: вернуть списки списков из рекурсивной функции

Question

Проблема

Мне трудно понять, как вернуть вложенный список из рекурсивной функции. У меня есть вложенная структура, из которой я хочу вернуть элементы с каждого уровня.

Input

У меня есть структура, подобная следующей, где я, однако, не знаю глубины.

# Data
my_input = {'a': {'d':None, 'e':None, 'f':{'g':None}}, 'b':None, 'c':None}

Вывод

Мне нужны все возможные уровни вывода в список списков

# Desired output
[['a'], ['b'], ['c'], ['a', 'd'], ['a', 'e'], ['a', 'f'], ['a', 'f', 'g']]

Что я пробовал

Эта функция не работает навсе. Кажется, я не могу понять, как вернуться из рекурсивной функции. Всякий раз, когда я запускаю функцию, я либо перезаписываю вывод, либо не получаю правильную информацию из предыдущей итерации. Любые предложения о том, как правильно написать эту функцию?

def output_levels(dictionary, output=None):
    print(dictionary)
    if not output:
        output = []
    if len(dictionary.keys()) == 1:
        return output.append(dictionary.keys())
    for key in dictionary.keys():
        if not dictionary[key]:
            output.append(key)
            continue
        output.append(output_levels(dictionary[key], output.append(key)))
    return output

Answer 1

Вы можете сделать:

my_input = {'a': {'d': None, 'e': None, 'f': {'g': None}}, 'b': None, 'c': None}


def paths(d, prefix=None):

     if prefix is None:
         prefix = []

     for key, value in d.items():
         if value is not None:
             yield prefix + [key]
             yield from paths(value, prefix=prefix + [key])
         else:
             yield prefix + [key]


print(sorted(paths(my_input), key=len))

Вывод

[['a'], ['b'], ['c'], ['a', 'd'], ['a', 'e'], ['a', 'f'], ['a', 'f', 'g']]

Answer 2

Просто мы можем сделать что-то вроде этого:

dictionary = {
    'a': {
        'd': None, 
        'e': None, 
        'f': {
            'g': None,
        },
    }, 
    'b': None, 
    'c': None,
}
expected_output = [
    ['a'], ['b'], ['c'], 
    ['a', 'd'], ['a', 'e'], ['a', 'f'], 
    ['a', 'f', 'g'],
]


def get_levels(dictionary, parents=[]):
    if not dictionary:
        return []

    levels = []

    for key, val in dictionary.items():
        cur_level = parents + [key]
        levels.append(cur_level)
        levels.extend(get_levels(val, cur_level))

    return levels


output = get_levels(dictionary)
print(output)
assert sorted(output) == sorted(expected_output)

Answer 3

Немного более короткий рекурсивный подход с yield:

my_input = {'a': {'d':None, 'e':None, 'f':{'g':None}}, 'b':None, 'c':None}
def get_paths(d, c = []):
  for a, b in getattr(d, 'items', lambda :[])():
     yield c+[a]
     yield from get_paths(b, c+[a])

print(list(get_paths(my_input)))

Вывод:

[['a'], ['a', 'd'], ['a', 'e'], ['a', 'f'], ['a', 'f', 'g'], ['b'], ['c']]