I want to convert this list:
[1,2,3,4,5]
Into this dict:
{ 1 :
{ 2 :
{ 3 :
{ 4 : 5 }}}}
This doesn't sound too complicated but I'm stumped when it's time to assign a value to a key deeper than the surface. I have a recursive function for finding how deep my dictionary goes but I don't know how to tell my algorithm to "add the new key here".
You are looking for a recursive function that builds a dictionary with the first list element as a key and the transformed rest of the list as the value:
l = [1, 2, 3, 4, 5]
def l2d(l):
if len(l) < 2: # Not good
raise Exception("The list is too short")
if len(l) == 2: # Base case
return {l[0]: l[1]}
# Recursive case
return {l[0]: l2d(l[1:])}
l2d(l)
# {1: {2: {3: {4: 5}}}}
Another interesting approach is to use functools.reduce:
from functools import reduce
reduce(lambda tail,head: {head: tail}, reversed(l))
# {1: {2: {3: {4: 5}}}}
It progressively applies a dictionary construction function to the first element of the list and the rest of it. The list is reversed first, so the construction naturally starts at the end. If the list is too short, the function returns its first element, which may or may not be desirable.
The "reduce" solution is MUCH FASTER, by about two orders of magnitude. The bottom line: avoid recursion.
There is no need for recursion to solve this. A simple loop is sufficient.
def nest(keys):
if not keys:
return {}
elif len(keys) == 1:
return key[0]
root = level = {}
for key in keys[:-1]:
level[key] = {}
level = level[key]
level[key] = keys[-1]
return root
Alternatively, you can build the dict inside-out:
def nest(keys):
if not keys:
return {}
current = keys[-1]
for key in keys[-2::-1]: # iterate keys in reverse
current = {key: current}
return current
That's a nice case to use the recursive logic until the length of your list is 1. For example:
Update: Fix empty list error.
A = [1, 2, 3, 4, 5]
def rec_dict(listA):
try:
if len(listA) <= 1:
listA = listA[0]
else:
listA = {listA.pop(0): rec_dict(listA)}
except IndexError:
pass
return listA
print(rec_dict(A))
Which returns:
{1: {2: {3: {4: 5}}}}
I want to propose another option using a different approach:
Although it's not recommend to use ast.literal_eval, I think in this case can be useful. Additionally, You can help yourself using re.sub() + re.findall() in order to find the matches and to do the replacements correctly. The idea here is using the string representation of the list.
import ast
import re
lst = [1, 2, 3, 4, 5]
lst_str = str(lst).replace("[","{").replace("]","}")
pattern_commas = re.compile(", ")
matches = re.findall(pattern_commas, lst_str)
n = len(matches) - 1
output = re.sub(pattern_commas, ':{', lst_str, n).replace(",",":") + '}' * n
dictionary = ast.literal_eval(output)
print(dictionary)
Output:
{1: {2: {3: {4: 5}}}}
EDIT: Before using this answer, please read @wjandrea's comment. This doesn't work for all inputs.
