CODEWITHSUNDEEP
pythondata-structures
sachinruk
sachinruk

Reputation: 9869

Nesting dictionary algorithm

Suppose I have the following dictionary:

{'a': 0, 'b': 1, 'c': 2, 'c.1': 3, 'd': 4, 'd.1': 5, 'd.1.2': 6}

I wish to write an algorithm which outputs the following:

{
    "a": 0,
    "b": 1,
    "c": {
        "c": 2,
        "c.1": 3
    },
    "d":{
        "d": 4,
        "d.1": {
            "d.1": 5,
            "d.1.2": 6
        }
    }
}

Note how the names are repeated inside the dictionary. And some have variable level of nesting (eg. "d").

I was wondering how you would go about doing this, or if there is a python library for this? I know you'd have to use recursion for something like this, but my recursion skills are quite poor. Any thoughts would be highly appreciated.

Upvotes: 0

Views: 101

Answers (3)

Ajax1234
Ajax1234

Reputation: 71451

Slightly shorter recursion approach with collections.defaultdict:

from collections import defaultdict
data = {'a': 0, 'b': 1, 'c': 2, 'c.1': 3, 'd': 4, 'd.1': 5, 'd.1.2': 6}
def group(d, p = []):
  _d, r = defaultdict(list), {}
  for n, [a, *b], c in d:
     _d[a].append((n, b, c))
  for a, b in _d.items():
     if (k:=[i for i in b if i[1]]):
        r['.'.join(p+[a])] = {**{i[0]:i[-1] for i in b if not i[1]}, **group(k, p+[a])}
     else:
        r[b[0][0]] = b[0][-1]
  return r
        
 
print(group([(a, a.split('.'), b) for a, b in data.items()]))

Output:

{'a': 0, 'b': 1, 'c': {'c': 2, 'c.1': 3}, 'd': {'d': 4, 'd.1': {'d.1': 5, 'd.1.2': 6}}}

Upvotes: 1

tobias_k
tobias_k

Reputation: 82899

You can use a recursive function for this or just a loop. The tricky part is wrapping existing values into dictionaries if further child nodes have to be added below them.

def nested(d):
    res = {}
    for key, val in d.items():
        t = res
        # descend deeper into the nested dict
        for x in [key[:i] for i, c in enumerate(key) if c == "."]:
            if x in t and not isinstance(t[x], dict):
                # wrap leaf value into another dict
                t[x] = {x: t[x]}
            t = t.setdefault(x, {})
        # add actual key to nested dict
        if key in t:
            # already exists, go one level deeper
            t[key][key] = val
        else:
            t[key] = val
    return res

Your example:

d = {'a': 0, 'b': 1, 'c': 2, 'c.1': 3, 'd': 4, 'd.1': 5, 'd.1.2': 6}
print(nested(d))
# {'a': 0,
#  'b': 1,
#  'c': {'c': 2, 'c.1': 3},
#  'd': {'d': 4, 'd.1': {'d.1': 5, 'd.1.2': 6}}}

Upvotes: 3

wwii
wwii

Reputation: 23753

Nesting dictionary algorithm ...
how you would go about doing this,

  • sort the dictionary items
  • group the result by index 0 of the keys (first item in the tuples)
  • iterate over the groups
    • if there are is than one item in a group make a key for the group and add the group items as the values.

Upvotes: 1

Related Questions