Generic Way To Create Nested Dictionary From Flat List In Python

I am looking for the simplest generic way to convert this python list: x = [ {'foo':'A', 'bar':'R', 'baz':'X'}, {'foo':'A', 'bar':'R', 'baz':'Y'}, {'foo':'B

Solution 1:

#!/usr/bin/env python3
from itertools import groupby
from pprint import pprint

x = [
        {"foo":"A", "bar":"R", "baz":"X"},
        {"foo":"A", "bar":"R", "baz":"Y"},
        {"foo":"B", "bar":"S", "baz":"X"},
        {"foo":"A", "bar":"S", "baz":"Y"},
        {"foo":"C", "bar":"R", "baz":"Y"},
    ]


def fun(x, l):
    ks = ['foo', 'bar', 'baz']
    kn = ks[l]
    kk = lambda i:i[kn]
    for k,g in groupby(sorted(x, key=kk), key=kk):
        kg = [dict((k,v) for k,v in i.items() if k!=kn) for i in g]
        d = {}
        d[kn] = k
        if l<len(ks)-1:
            d[ks[l+1]+'s'] = list(fun(kg, l+1))
        yield d

pprint(list(fun(x, 0)))

---

[{'bars': [{'bar': 'R', 'bazs': [{'baz': 'X'}, {'baz': 'Y'}]},
           {'bar': 'S', 'bazs': [{'baz': 'Y'}]}],
  'foo': 'A'},
 {'bars': [{'bar': 'S', 'bazs': [{'baz': 'X'}]}], 'foo': 'B'},
 {'bars': [{'bar': 'R', 'bazs': [{'baz': 'Y'}]}], 'foo': 'C'}]

---

note: dict is unordered! but it's the same as yours.

Solution 2:

I would define a function that performs a single grouping step like this:

from itertools import groupby
defgroup(items, key, subs_name):
    return [{
        key: g,
        subs_name: [dict((k, v) for k, v in s.iteritems() if k != key)
            for s in sub]
    } for g, sub in groupby(sorted(items, key=lambda item: item[key]),
        lambda item: item[key])]

and then do

[{'foo': g['foo'], 'bars': group(g['bars'], "bar", "bazs")} for g ingroup(x,
     "foo", "bars")]

which gives the desired result for foos.

Solution 3:

This is a simple loop over the data, no recursion. An auxiliary tree where the values are dictionary keys is used as an index to the result tree while it is being built.

def make_tree(diclist, keylist):
    indexroot = {}
    root = {}
    for d in diclist:
        walk = indexrootparent= root
        for k in keylist:
            walk = walk.setdefault(d[k], {})
            node = walk.setdefault('node', {})
            if not node:
                node[k] = d[k]
                parent.setdefault(k+'s',[]).append(node)
            walk = walk.setdefault('children', {})
            parent = node
    return root[keylist[0]+'s']

foos = make_tree(x, ["foo","bar","baz"])