Return lists of lists from recursive function

Question

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

Dani Mesejo · Accepted Answer · 2019-10-03 08:24:11Z

6

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']]

answered Oct 3, 2019 at 8:24

Dani Mesejo

62.2k6 gold badges56 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Akash Pagar Over a year ago

@Daniel I don't get this, why you are using yield?

Dani Mesejo Over a year ago

@AkashPagar For me is easier to to use yield when thinking of recursive functions.

Esben Eickhardt Over a year ago

I just implemented it for my problem with win32.com, and it works like a charm <3 I must admit that I didn't understand the yield part either.

Dani Mesejo Over a year ago

@EsbenEickhardt yield allows you to return values, without actually finishing the execution of the function, this way I don't have to worry about keep a third variable for the output list

Esben Eickhardt Over a year ago

Ahh, makes sense. It was that third ouput-list-variable that kept messing me up :)

Dipen Dadhaniya · Accepted Answer · 2019-10-03 08:37:08Z

2

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)

edited Oct 3, 2019 at 8:37

answered Oct 3, 2019 at 8:31

Dipen Dadhaniya

4,6602 gold badges19 silver badges26 bronze badges

Comments

Ajax1234 · Accepted Answer · 2019-10-03 14:43:59Z

0

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']]

answered Oct 3, 2019 at 14:43

Ajax1234

71.7k9 gold badges67 silver badges110 bronze badges

Collectives™ on Stack Overflow

Return lists of lists from recursive function

Problem

Input

Output

What I have tried

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Problem

Input

Output

What I have tried

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related