Skip to content
Advertisement

Python: Building list of lists using dictionary recursion

I have a very complicated problem that I am sort of hoping to rubberduck here:

I have a dictionary:

{
    "1": {
        "1.1": {
            "1.1.1": {}
        },
        "1.2": {
            "1.2.1": {}
        }
    },
    "2": {
        "2.1": {
            "2.1.1": {}
        },
        "2.2": {
            "2.2.2": {}
        }
    }
}

whose structure wont always be the same (i.e., there could be further nesting or more keys in any sub-dictionary). I need to be able to generate a specifically ordered list of lists (contained sub-lists need not be ordered) based on some input. The structure of the lists is based on the dictionary. Accounting for all keys in the dictionary, the list of lists would look like:

[['1', '2'], ['1.2', '1.1'], ['1.1.1'], ['1.2.1'], ['2.2', '2.1'], ['2.1.1'], ['2.2.2']]

That is, the first sublist contains the two keys at the highest level of the dictionary. The second sub-list contains the two keys under the first “highest level” key. The third and fourth sub-lists contain the keys available under the “2nd level” of the dictionary. (And so on)

I need a function that, based on input (that is any key in the nested dictionary), will return the correct list of lists. For example(s):

function('2.2.2')
>>> [['2'], None, None, None, ['2.2'], None, ['2.2.2']] # or [['2'], [], [], [], ['2.2'], [], ['2.2.2']]

function('1.1')
>>> [['1'], ['1.1'], None, None, None, None, None] # or [['1'], ['1.1'], [], [], [], [], []]

function('1.2.1')
>>> [['1'], ['1.2'], None, ['1.2.1'], None, None, None] # or [['1'], ['1.2'], [], ['1.2.1'], None, [], []]

It is almost like I need to be able to “know” the structure of the dictionary as I recurse. I keep thinking maybe if I can find the input key in the dictionary and then trace it up, I will be able to generate the list of lists but

  1. how can I recurse “upwards” in the dictionary and
  2. how in the world do I store the information in the lists as I “go along”?

Advertisement

Answer

Your master list is just a depth-first list of all the keys in your dict structure. Getting this is fairly easy:

def dive_into(d):
    if d and isinstance(d, dict):
        yield list(d.keys())
        for v in d.values():
            yield from dive_into(v)


d = {
    "1": {
        "1.1": {
            "1.1.1": {}
        },
        "1.2": {
            "1.2.1": {}
        }
    },
    "2": {
        "2.1": {
            "2.1.1": {}
        },
        "2.2": {
            "2.2.2": {}
        }
    }
}

master_list = list(dive_into(d))
# [['1', '2'], ['1.1', '1.2'], ['1.1.1'], ['1.2.1'], ['2.1', '2.2'], ['2.1.1'], ['2.2.2']]

Next, your function needs to find all the parent keys of the given key, and only return the keys that are in the path to the given key. Since your keys always have the format <parent>.<child>.<grandchild>, you only need to iterate over this list, and return any elements e for which key.startswith(e) is True:

def function(key):
    lst = [[e for e in keys if key.startswith(e)] for keys in master_list]
    return [item or None for item in lst]

Testing this with your examples:

>>> function('2.2.2')
Out: [['2'], None, None, None, ['2.2'], None, ['2.2.2']]

>>> function('1.1')
Out: [['1'], ['1.1'], None, None, None, None, None]

>>> function('1.2.1')
Out: [['1'], ['1.2'], None, ['1.2.1'], None, None, None]
Advertisement