Recursive function for converting a nested list to a nested dictionary

Question

I have a list of lists and I want to get a dictionary of dictionaries:

import json

list = [
        ['1', '2', '3'],
        ['a', 'b'],
        ['I', 'II'],
        ['A', 'B', 'C'],
        ['A', 'B', 'D']
    ]

dict = {}  
    
for val in list:
    count = len(val)
    if val[0] not in dict:
        dict[val[0]] = {}
    if count == 3:
        if val[1] not in dict[val[0]]:
            dict[val[0]][val[1]] = {}
        if val[2] not in dict[val[0]][val[1]]:
            dict[val[0]][val[1]][val[2]] = ''
    else:
        if val[1] not in dict[val[0]]:
            dict[val[0]][val[1]] = ''
            
print (json.dumps(dict, sort_keys=True, indent=4))

output:

{
    "1": {
        "2": {
            "3": ""
        }
    },
    "A": {
        "B": {
            "C": "",
            "D": ""
        }
    },
    "I": {
        "II": ""
    },
    "a": {
        "b": ""
    }
}

So it works with 2 or 3 elements in lists, but if I have more (random) elements of lists, I have to have kind of recursive function, that I can't think of.

Answer 1

I did this rudimentary logic recursion function. Which I tested for your sample input to work well.

def subdict(dic,val):
    if len(val)==1:
        dic.update({val[0]:""})
    else:
        if val[0] not in dic.keys():
            dic.update({val[0]:{}})
        subdict(dic[val[0]],val[1:])

full execution:

lists = [
        ['1', '2', '3'],
        ['a', 'b'],
        ['I', 'II'],
        ['A', 'B', 'C'],
        ['A', 'B', 'D']
    ]

rootdict = {}

def subdict(dic,val):
    if len(val)==1:
        dic.update({val[0]:""})
    else:
        if val[0] not in dic.keys():
            dic.update({val[0]:{}})
        subdict(dic[val[0]],val[1:])


for li in lists:
    subdict(rootdict,li)

print(rootdict)

Output:

{'1': {'2': {'3': ''}}, 'a': {'b': ''}, 'I': {'II': ''}, 'A': {'B': {'C': '', 'D': ''}}}

Explainaton:

subdict function :

• Checks if we have reached the end, then it happily terminates this leaf of recursion by adding the final entry of key with value ''
• if we aren't at the end leaf, it checks if the key[0] is not present in this level of the dict and if so it adds that key. Then finally recursively proceeds for the next iteration, further deep down.

I know this is boring logic, but it works :)

Answer 2

As Tomerikoo said, you don't have to use a recursion, but if you want to solve it using recursion, you should define a recursion function, with your base case - last element in a list.

Then iterate your input (list of lists), and pass the current working list to the recursive function.

UPDATE: thanks to a bug Tomerikoo found, I had to fix my answer. When you use .update() method of a dict, it doesn't do "deepcopy" of the values. So you have to implement it yourself, with another recursion :-)

You need to implement a merge_dict function that, before updating the result. The function below takes two dicts, and merge them using deepcopy. I'll try to simplify the steps:

1. Iterate the second dict items, if the value is a dict then -
2. Check if the key already exists in the result, if not create an empty dict, and call the merge function again
3. If the value is not a dict - simply add it to the result dict.

---

import json
from copy import deepcopy

final_dict = {}
my_list = [
    ['1', '2', '3'],
    ['a', 'b'],
    ['I', 'II'],
    ['A', 'B', 'C'],
    ['A', 'B', 'D']
]


def nested_dict(a_list):
    if len(a_list) == 1:
        print("base case: {}".format(a_list))
        return {a_list[0]: ""}

    return {a_list[0]: nested_dict(a_list[1:])}


def merge_dicts(d1, d2):
    res = deepcopy(d1)

    for k, v in d2.items():
        if isinstance(v, dict):
            res[k] = merge_dicts(res.get(k, {}), v)
        else:
            res[k] = v

    return res


for sub in my_list:
    my_dict = nested_dict(sub)
    final_dict = merge_dicts(final_dict, my_dict)


print("final dict: {}".format((json.dumps(final_dict, sort_keys=True, indent=4))))

Answer 3

There is no real need for a recursive function here (unless it's a requirement). You also don't need to care for the size or amount of lists. Simply iterate through each list while keeping an updated reference for the inner dicts as you go.

You can also use setdefault to avoid the checks if a key exists already.

d = {}
for sub in l:
    inner = d
    for elem in sub[:-1]:
        inner = inner.setdefault(elem, {})
        
    inner[sub[-1]] = ""

---

If for some reason you really want this as a recursive function, then the following is an equivalent version. It starts off with a base dict, and with each call creates an inner dict and the next call goes down one level of the dict and passes the rest of the list. The base-case is when the list has one element so the string is used instead of a dict. Again, for simplicity, setdefault is used:

def create_dict(l, d):
    if len(l) == 1:
        d[l[0]] = ""
    else:
        d = d.setdefault(l[0], {})
        create_dict(l[1:], d)

d = {}
for sub in l:
    create_dict(sub, d)

---

^{Try to avoid using built-in names for variables. Both list and dict represent the respective class' constructor which are not any more available in your program.}