Home > Back-end >  Python: Parsing Dictionary Recursively
Python: Parsing Dictionary Recursively

Time:07-20

I have a dictionary that I would like to parse recursively and build a structure of Dash components (knowledge of the components is unnecessary as long as you know that .children is a list). I am able to figure out how to do it a couple levels down but this will get tedious as the dictionary becomes large. How can I handle this recursively (or can I)?

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

C = dbc.Accordion([])
for i in d.keys():

    B = dbc.Accordion([])
    for j in d[i].keys():
        
        A = dbc.Accordion([])
        for k in d[i][j].keys():

            A.children.append(dbc.AccordionItem([], title=k))
            
        B.children.append(dbc.AccordionItem(A, title=j))

    C.children.append(dbc.AccordionItem(B, title=i))
        
print(C) 

(There might be a better title for my question)

EDIT: The accordion objects allow me to create a nested menu:

enter image description here

When I print(C), this is the output I need:

Accordion(children=[AccordionItem(children=Accordion(children=[AccordionItem(children=Accordion(children=[AccordionItem(children=[], title='1.1.1')]), title='1.1'), AccordionItem(children=Accordion(children=[AccordionItem(children=[], title='1.2.1')]), title='1.2')]), title='1'), AccordionItem(children=Accordion(children=[AccordionItem(children=Accordion(children=[AccordionItem(children=[], title='2.1.1')]), title='2.1'), AccordionItem(children=Accordion(children=[AccordionItem(children=[], title='2.2.2')]), title='2.2')]), title='2')])

EDIT 2:

Here is some code that allows demonstration of what I need without needing the dbc module (this is important because as I recurse through the dictionary I need to be able to use these different datatypes - that behave like lists):

class Accordion:
    def __init__(self, list_):
        self.list_ = list_

    def __str__(self):
        return f'Accordion({self.list_})'
    
    def append_(self, item):
        return self.list_.append(item)
    
   
class AccordionItem:
   def __init__(self, list_, title):
        self.list_ = list_
        self.title = title

   def __repr__(self):
        return f"AccordionItem('{self.list_}', title='{self.title}')"
    
    
d = {'1': {'1.1': {'1.1.1': {}}, '1.2': {'1.2.1': {}}}, 
  '2': {'2.1': {'2.1.1': {}}, '2.2': {'2.2.2': {}}}}

C = Accordion([])
for i in d.keys():

    B = Accordion([])
    for j in d[i].keys():
        
        A = Accordion([])
        for k in d[i][j].keys():

            A.append_(AccordionItem([], k))
            
        B.append_(AccordionItem(A, j))

    C.append_(AccordionItem(B, i))
        
print(C) 

CodePudding user response:

For recursive problems that can recurse arbitrarily deep, you can use a function that calls itself (as this can happen however many times*).

*: python has a "recursion limit" of 1000. This won't be a problem unless if you have dictionaries that exceed 1000 levels of nesting (the length of the dictionary can still exceed 1000). See here for more information.

Here's an example of how you might go about using recursive functions. I'm not sure what output you are trying to achieve and I'm not familiar with accordions so I am using regular python lists for a similar recursive problem. The principles are the same, however, so hopefully you can figure out how to adapt it to your specific problem:

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

def generate_accordion(input_dictionary):
    output = []

    for subdict in input_dictionary.values():
        # dict.values() instead of dict.keys() to keep it simple 

        output.append(generate_accordion(subdict))
        # The recursive part - calls itself. Explanation Below

    return output

C = generate_accordion(d)
print(C)

EXPLANATION

Recursive functions can be a bit confusing at first. Here is a general idea of how the function works:

  1. The function starts by creating a blank list called output.
  2. Then, the function starts to iterate through each value in the dictionary. It iterates through the values rather than the keys like in your example.
  3. For each sub dictionary within the original dictionary, it will call the function again. While iterating through d, it will start by calling generate_accordion for d['1'] (i.e., {'1.1': {'1.1.1': {}}}). Then, in that function call, it will call the function for each subdictionary within d['1'], starting (and ending, since d['1'] is of length 1) with d['1']['1.1'] (i.e. {'1.1.1': {}}). Then, in that call, it will call the function for {}.
  4. It will keep recursing until it has reached a dictionary with no sub dictionaries, as then input_dictionary.values() will be empty, so the function will skip the iteration and immediately return [].
  5. This will then be appended to output in the second to last recursion depth and the function will continue to iterate through all subdictionaries at every level, and each time the function is called it will continue to recurse until it reaches an empty dictionary.
  6. The function will return a value only if either the dictionary passed in it is empty or if it has iterated and recursed through all subdictionaries down to the aforementioned point where the dictionary has no dictionaries within it.

The output (below) is a sort of "depth map" for the dictionary, with nested arrays corresponding to the dictionary depth in different areas:

[[[[]], [[]]], [[[]], [[]]]]

When you write your own recursive algorithms, be sure to include a stopping point. This recursive algorithm has a stopping point when there are no subdictionaries within the passed in dictionary, but not all recursive algorithms will have natural stopping point.

If you need more information about recursion or would like to learn more, look at this video.

CodePudding user response:

The final code ended up looking like this:

def generate_accordion(input_dictionary):
    output = dbc.Accordion([])

    for key, subdict in input_dictionary.items():
        output.children.append(dbc.AccordionItem(generate_accordion(subdict), title=key))
    return output
C = generate_accordion(d)
print(C)
  • Related