Общий способ создания вложенного словаря из плоского списка в Python

Question

Я ищу самый простой универсальный способ преобразования этого списка Python:

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"},
    ]

в:

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"} ] },
                            ]
         },
      ]

Комбинация "foo", "bar "," baz "является уникальным, и, как вы можете видеть, список не обязательно упорядочен этим ключом.

Answer 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'}]

---

примечание: dict неупорядочено!но он такой же как у тебя.

Answer 2

Это простой цикл по данным, без рекурсии. Вспомогательное дерево, значения которого являются ключами словаря, используется в качестве индекса для дерева результатов во время его построения.

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"])

Answer 3

Я бы определил функцию, которая выполняет один шаг группировки следующим образом:

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])]

и затем

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

, который дает желаемый результат для foos.