Построение списка с родитель-ребенок зависимости

Question

У меня есть список dicts, который выглядит примерно так:

list = [{'parent': u'#5963','id': 5962},{'parent': u'','id': 5963}, 
{'parent': u'#5963', 'id': 5964}, {'parent': u'#5966', 'id': 5967}, 
{'parent': u'#5963','id': 5966}, {'parent': u'#5962','id': 5968} ] 

Фактические dicts немного сложнее - у них есть несколько ключей и значений.

Как вы можете видеть - каждый dict имеет «родительский» ключ, который сообщает нам идентификатор родительского элемента и ключ «id».

Теперь вопрос заключается в следующем: возможно ли создать новый список (или отсортировать его) таким образом, чтобы все dicts помещались в родительско-дочерний путь?

Таким образом, новый ДИКТ будет:

[{'parent': u'','id': 5963},{'parent': u'#5963','id': 5962}, 
{'parent': u'#5962','id': 5968}, {'parent': u'#5963', 'id': 5964}, 
{'parent': u'#5963','id': 5966}, {'parent': u'#5966', 'id': 5967} ] 

PS: Там может быть не корневые элементы (элементы с ключом «родительского» = «»)
PPS: Родительский элемент не могут иметь более 1-2 уровней детей

Answer 1

Вы не можете сделать это прямолинейно, сначала создайте дерево из своего списка. Вам нужны два информации: список лучших узлов (либо узел без родителя или ребенка с несуществующим родителем) в дереве и родители/детях соотношении:

def build_tree(l): 
    exists = set(map(lambda x : x['id'], l)) 

    tops = [] 
    children = {} 
    for e in l: 
     parent = e['parent'] 
     if not parent: 
      tops.append(e) 
      continue 

     parent = int(parent[1:]) 
     if parent not in exists: 
      tops.append(e) 
      continue 

     if parent in children: 
      children[parent].append(e) 
     else: 
      children[parent] = [ e ] 

    return children, tops 

Затем сделать глубину первого обхода этого дерева с рекурсивной функцией:

def build_list(children, top): 
    l = [ top ] 
    if top['id'] in children: 
     for child in children[top['id']]: 
      l += build_list(children, child) 
    return l 

Первая функция даст вам структуру дети/отношение, а второй позволит вам создать список для каждого возможного верхнего узла.

Теперь вы можете отсортировать список, используя эти две функции:

l = [{'parent': u'#5963','id': 5962},{'parent': u'','id': 5963}, 
{'parent': u'#5963', 'id': 5964}, {'parent': u'#5966', 'id': 5967}, 
{'parent': u'#5963','id': 5966}, {'parent': u'#5962','id': 5968} ] 
children, tops = build_tree(l) 
for top in tops: 
    print build_list(children, top) 
# outputs : [{'id': 5963, 'parent': u''}, {'id': 5962, 'parent': u'#5963'}, 
# {'id': 5968, 'parent': u'#5962'}, {'id': 5964, 'parent': u'#5963'}, 
# {'id': 5966, 'parent': u'#5963'}, {'id': 5967, 'parent': u'#5966'}] 

Если удалить узел 5963, который даст:

[{'id': 5962, 'parent': u'#5963'}, {'id': 5968, 'parent': u'#5962'}] 
[{'id': 5964, 'parent': u'#5963'}] 
[{'id': 5966, 'parent': u'#5963'}, {'id': 5967, 'parent': u'#5966'}]