CODEWITHSUNDEEP
pythonpython-3.x
MrPoulet
MrPoulet

Reputation: 91

Convert a list into a dict where each key is nested under the next one

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".

Upvotes: 4

Views: 178

Answers (4)

Georgios Livanos
Georgios Livanos

Reputation: 536

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}}}}

Upvotes: 1

MisterMiyagi
MisterMiyagi

Reputation: 52169

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

Upvotes: 2

Carmoreno
Carmoreno

Reputation: 1319

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.

Upvotes: 0

DYZ
DYZ

Reputation: 57125

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.

Upvotes: 6

Related Questions