How to convert nested dictionary into the string of list-CodePudding

I have this nested python dictionary

dictionary = {'a':'1', 'b':{'c':'2', 'd':{'z':'5',  'e':{'f':'13', 'g':'14'}}}}

So the recommended output will be:

output = ['a:1', 'b:c:2', 'b:d:z:5', 'b:d:e:f:13', 'b:d:e:g:13']

using recursive function and without using recursive function

CodePudding user response：

In cases like this, I always like to try and solve the easy part first.

def flatten_dict(dictionary):
    output = []
    for key, item in dictionary.items():
        if isinstance(item, dict):
            output.append(f'{key}:???')  # Hm, here is the difficult part
        else:
            output.append(f'{key}:{item}')
    return output

Trying flatten_dict(dictionary) now prints ['a:1', 'b:???'] which is obviously not good enough. For one thing, the list has three items too few.

First, I'd like to switch to using generator functions. This is more complicated for now, but will pay off later.

def flatten_dict(dictionary):
    return list(flatten_dict_impl(dictionary))

def flatten_dict_impl(dictionary):
    for key, item in dictionary.items():
        if isinstance(item, dict):
            yield f'{key}:???'
        else:
            yield f'{key}:{item}'

No change in the output yet. Time to go recusrive.

You want the output to be a flat list, so that means we have to yield multiple things in the case item is a dictionary. Only, what things? Let's try plugging in a recursive call to flatten_dict_impl on this subdictionary, that seems the most straightforward way to go.

# flatten_dict is unchanged

def flatten_dict_impl(dictionary):
    for key, item in dictionary.items():
        if isinstance(item, dict):
            for value in flatten_dict_impl(item):
                yield f'{key}:{value}'
        else:
            yield f'{key}:{item}'

The output is now ['a:1', 'b:c:2', 'b:d:z:5', 'b:d:e:f:13', 'b:d:e:g:14'], which is the output you wanted, except the final 14, but I think that's a typo on your part.

Now the non-recursive route. For that we need to manage some state ourselves, because we need to know how deep we are.

def flatten_dict_nonrecursive(dictionary):
    return list(flatten_dict_nonrecursive_impl(dictionary))

def flatten_dict_nonrecursive_impl(dictionary):
    dictionaries = [iter(dictionary.items())]
    keys = []
    while dictionaries:
        try:
            key, value = next(dictionaries[-1])
        except StopIteration:
            dictionaries.pop()
            if keys:
                keys.pop()
        else:
            if isinstance(value, dict):
                keys.append(key)
                dictionaries.append(iter(value.items()))
            else:
                yield ':'.join(keys   [key, value])

Now this gives the right output but is a lot less easy to understand, and a lot longer. It took a lot longer for me to get right too. There may be shorter and more obvious ways to do it that I missed, but in general recursive problems are easier to solve with recursive functions.

Such an approach can still be useful: if your dictionaries are nested hundreds or thousands of levels deep, then trying to do it recursively will likely overflow the stack.

I hope this helps. Let me know if I need to go into more detail or something.