CODEWITHSUNDEEP
pythonlistdictionaryrecursionnested
Esben Eickhardt
Esben Eickhardt

Reputation: 3852

Return lists of lists from recursive function

Problem

I have a hard time figuring out how to return a nested list from a recursive function. I have a nested structure, from which I want to return elements from each level.

Input

I have a structure similar to the following, where I however do not know the depth.

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

Output

I need all possible levels output to a list of lists

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

What I have tried

This function does not work at all. It seems I am not able to get my head around how to return from a recursive function. Whenever I run through the function I end up either overwriting the output, or not having the correct information from the previous iteration. Any suggestions of how to write this function properly?

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

Upvotes: 0

Views: 121

Answers (3)

Ajax1234
Ajax1234

Reputation: 71451

Slightly shorter recursive approach with 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)))

Output:

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

Upvotes: 0

Dipen Dadhaniya
Dipen Dadhaniya

Reputation: 4630

Simply we can do something like this:

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)

Upvotes: 2

Dani Mesejo
Dani Mesejo

Reputation: 61910

You could do:

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

Output

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

Upvotes: 6

Related Questions