Python: Building list of lists using dictionary recursion

Question

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

how can I recurse "upwards" in the dictionary and
how in the world do I store the information in the lists as I "go along"?

That's fine - you were hoping to rubberduck the problem here, and that requires you to share your attempt (or at least your thought process) — pho
– pho, Commented Jul 26, 2022 at 16:33
Then you don't need to "know" the structure of the dictionary because the argument to function tells you which keys to drill down into: With x = key.split('.'), the ith level will have the key '.'.join(x[:i+1]) — pho
– pho, Commented Jul 26, 2022 at 16:45

pho · Accepted Answer · 2022-07-26 18:10:09Z

2

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]

edited Jul 26, 2022 at 18:10

answered Jul 26, 2022 at 16:47

pho

25.7k8 gold badges48 silver badges75 bronze badges

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

5 Comments

Dani Mesejo Over a year ago

What happens if the first key is "2" instead of "1"

Scott Hunter Over a year ago

This only solves part of the problem.

pho Over a year ago

@DaniMesejo I'm not sure what you mean

pho Over a year ago

@ScottHunter I had two tabs on this question and accidentally clicked "post" in the wrong one.

Sterling Butters Over a year ago

@PranavHosangadi What the heck, you did that so fast... Thanks so much! I am looking at your explanation now

Collectives™ on Stack Overflow

Python: Building list of lists using dictionary recursion

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related