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", "bar":"S", "baz":"X"},
{"foo":"A", "bar":"S", "baz":"Y"},
{"foo":"C", "bar":"R", "baz":"Y"},
]
into:
foos = [
{"foo":"A", "bars":[
{"bar":"R", "bazs":[ {"baz":"X"},{"baz":"Y"} ] },
{"bar":"S", "bazs":[ {"baz":"Y"} ] },
]
},
{"foo":"B", "bars":[
{"bar":"S", "bazs":[ {"baz":"X"} ] },
]
},
{"foo":"C", "bars":[
{"bar":"R", "bazs":[ {"baz":"Y"} ] },
]
},
]
The combination "foo","bar","baz" is unique, and as you can see the list is not necessarily ordered by this key.
#!/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.
I would define a function that performs a single grouping step like this:
from itertools import groupby
def group(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 in group(x,
"foo", "bars")]
which gives the desired result for foos .
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 = indexroot
parent = 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"])