Problema

Me resulta difícil descubrir cómo devolver una lista anidada de una función recursiva. Tengo una estructura anidada, desde la cual quiero devolver elementos de cada nivel.

Entrada

Tengo una estructura similar a la siguiente, donde sin embargo no sé la profundidad.

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

Salida

Necesito todos los niveles posibles de salida a una lista de listas

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

Lo que he intentado

Esta función no funciona en absoluto. Parece que no puedo entender cómo regresar de una función recursiva. Cada vez que ejecuto la función termino sobrescribiendo la salida o no tengo la información correcta de la iteración anterior. ¿Alguna sugerencia de cómo escribir esta función correctamente?

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
0
Esben Eickhardt 3 oct. 2019 a las 11:01

3 respuestas

La mejor respuesta

Podrías hacer lo:

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

Salida

[['a'], ['b'], ['c'], ['a', 'd'], ['a', 'e'], ['a', 'f'], ['a', 'f', 'g']]
5
Dani Mesejo 3 oct. 2019 a las 08:24

Enfoque recursivo ligeramente más corto con 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)))

Salida:

[['a'], ['a', 'd'], ['a', 'e'], ['a', 'f'], ['a', 'f', 'g'], ['b'], ['c']]
0
Ajax1234 3 oct. 2019 a las 14:43

Simplemente podemos hacer algo como esto:

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)
2
Dipen Dadhaniya 3 oct. 2019 a las 08:37
58214795