Как правильно написать рекурсию в Python для сбора элементов по parent key?

Question

[alexandrsemen4ukk]

не могу реализовать рекурсию...
есть список словарей, которые связываются друг с другом через Parent_Key.
По своей сути они являются справочниками в 1С, и реализуют один класс, разница только в том, что у них атрибут IsFolder True либо False - это всё отличие словарей. Как бы мне так красиво и без головных болей конвертировать такой список словарей в нормальное древо. Чтобы я мог обратиться к родителю и получить все элементы?

Написал вот такую рекурсию:

def test(listItems, parent):
    children = []
    for k, v in enumerate(listItems):
        if v['Parent_Key'] == parent:
            children.append({v['Description']: test(listItems, v['Ref_Key'])})
    return children

Входные данные:

[{'Ref_Key': '33ed0832-9697-11eb-8568-18c04d0357e4', 'DataVersion': 'AAABRgAAAAA=', 'DeletionMark': False, 'Parent_Key': 'a888a6c7-bb96-11ea-834d-f0795994df35', 'IsFolder': True, 'Code': 'СГ-000359', 'Description': '1.1. Затраты на приобретение прав на ЗУ ', 'ВидДеятельностиДляНалоговогоУчетаЗатрат': None, 'ВидРасходовНУ': None, 'РеквизитДопУпорядочивания': '12', 'Код_Добавленный': '', 'Синтека_projectId': '', 'Predefined': False, 'PredefinedDataName': '', 'Parent@navigationLinkUrl': "Catalog_СтатьиЗатрат(guid'33ed0832-9697-11eb-8568-18c04d0357e4')/Parent"}, {'Ref_Key': '33ed0834-9697-11eb-8568-18c04d0357e4', 'DataVersion': 'AAABSAAAAAA=', 'DeletionMark': False, 'Parent_Key': 'a888a6c7-bb96-11ea-834d-f0795994df35', 'IsFolder': True, 'Code': 'СГ-000361', 'Description': '1.5. Затраты на аренду ЗУ ', 'ВидДеятельностиДляНалоговогоУчетаЗатрат': None, 'ВидРасходовНУ': None, 'РеквизитДопУпорядочивания': '13', 'Код_Добавленный': '', 'Синтека_projectId': '', 'Predefined': False, 'PredefinedDataName': '', 'Parent@navigationLinkUrl': "Catalog_СтатьиЗатрат(guid'33ed0834-9697-11eb-8568-18c04d0357e4')/Parent"}, {'Ref_Key': '33ed0836-9697-11eb-8568-18c04d0357e4', 'DataVersion': 'AAABSgAAAAA=', 'DeletionMark': False, 'Parent_Key': 'a888a6c7-bb96-11ea-834d-f0795994df35', 'IsFolder': True, 'Code': 'СГ-000363', 'Description': '1.6. Затраты на изменение ВРИ.Проектирование', 'ВидДеятельностиДляНалоговогоУчетаЗатрат': None, 'ВидРасходовНУ': None, 'РеквизитДопУпорядочивания': '14', 'Код_Добавленный': '', 'Синтека_projectId': '', 'Predefined': False, 'PredefinedDataName': '', 'Parent@navigationLinkUrl': "Catalog_СтатьиЗатрат(guid'33ed0836-9697-11eb-8568-18c04d0357e4')/Parent"}, {'Ref_Key': '33ed0838-9697-11eb-8568-18c04d0357e4', 'DataVersion': 'AAABTAAAAAA=', 'DeletionMark': False, 'Parent_Key': 'a888a6c7-bb96-11ea-834d-f0795994df35', 'IsFolder': True, 'Code': 'СГ-000365', 'Description': '1.8. Прочие затраты на улучшения и содержание ЗУ', 'ВидДеятельностиДляНалоговогоУчетаЗатрат': None, 'ВидРасходовНУ': None, 'РеквизитДопУпорядочивания': '15', 'Код_Добавленный': '', 'Синтека_projectId': '', 'Predefined': False, 'PredefinedDataName': '', 'Parent@navigationLinkUrl': "Catalog_СтатьиЗатрат(guid'33ed0838-9697-11eb-8568-18c04d0357e4')/Parent"}]

Выходные данные:
(то как сейчас у меня выводится)

{'1.1. Затраты на приобретение прав на ЗУ ': [{'1.1. Затраты на приобретение прав на ЗУ': {'Ref_Key': '33ed0833-9697-11eb-8568-18c04d0357e4', 'DataVersion': 'AAABRwAAAAA=', 'DeletionMark': False, 'Parent_Key': '33ed0832-9697-11eb-8568-18c04d0357e4', 'IsFolder': False, 'Code': 'СГ-000360', 'Description': '1.1. Затраты на приобретение прав на ЗУ', 'ВидДеятельностиДляНалоговогоУчетаЗатрат': 'ОсновнаяСистемаНалогообложения', 'ВидРасходовНУ': 'МатериальныеРасходы', 'РеквизитДопУпорядочивания': '1', 'Код_Добавленный': '1.1.', 'Синтека_projectId': '', 'Predefined': False, 'PredefinedDataName': '', 'Parent@navigationLinkUrl': "Catalog_СтатьиЗатрат(guid'33ed0833-9697-11eb-8568-18c04d0357e4')/Parent"}}]}

{'1.5. Затраты на аренду ЗУ ': [{'1.5. Затраты на аренду ЗУ ': {'Ref_Key': '33ed0835-9697-11eb-8568-18c04d0357e4', 'DataVersion': 'AAABSQAAAAA=', 'DeletionMark': False, 'Parent_Key': '33ed0834-9697-11eb-8568-18c04d0357e4', 'IsFolder': False, 'Code': 'СГ-000362', 'Description': '1.5. Затраты на аренду ЗУ ', 'ВидДеятельностиДляНалоговогоУчетаЗатрат': 'ОсновнаяСистемаНалогообложения', 'ВидРасходовНУ': 'МатериальныеРасходы', 'РеквизитДопУпорядочивания': '1', 'Код_Добавленный': '1.5. ', 'Синтека_projectId': '', 'Predefined': False, 'PredefinedDataName': '', 'Parent@navigationLinkUrl': "Catalog_СтатьиЗатрат(guid'33ed0835-9697-11eb-8568-18c04d0357e4')/Parent"}}]}

{'1.6. Затраты на изменение ВРИ.Проектирование': [{'1.6. Затраты на изменение ВРИ.Проектирование': {'Ref_Key': '33ed0837-9697-11eb-8568-18c04d0357e4', 'DataVersion': 'AAABSwAAAAA=', 'DeletionMark': False, 'Parent_Key': '33ed0836-9697-11eb-8568-18c04d0357e4', 'IsFolder': False, 'Code': 'СГ-000364', 'Description': '1.6. Затраты на изменение ВРИ.Проектирование', 'ВидДеятельностиДляНалоговогоУчетаЗатрат': 'ОсновнаяСистемаНалогообложения', 'ВидРасходовНУ': 'МатериальныеРасходы', 'РеквизитДопУпорядочивания': '1', 'Код_Добавленный': '1.6. ', 'Синтека_projectId': '', 'Predefined': False, 'PredefinedDataName': '', 'Parent@navigationLinkUrl': "Catalog_СтатьиЗатрат(guid'33ed0837-9697-11eb-8568-18c04d0357e4')/Parent"}}]}

{'1.8. Прочие затраты на улучшения и содержание ЗУ': [{'1.8. Прочие затраты на улучшения и содержание ЗУ': {'Ref_Key': '33ed0839-9697-11eb-8568-18c04d0357e4', 'DataVersion': 'AAABTQAAAAA=', 'DeletionMark': False, 'Parent_Key': '33ed0838-9697-11eb-8568-18c04d0357e4', 'IsFolder': False, 'Code': 'СГ-000366', 'Description': '1.8. Прочие затраты на улучшения и содержание ЗУ', 'ВидДеятельностиДляНалоговогоУчетаЗатрат': 'ОсновнаяСистемаНалогообложения', 'ВидРасходовНУ': 'МатериальныеРасходы', 'РеквизитДопУпорядочивания': '1', 'Код_Добавленный': '1.8. ', 'Синтека_projectId': '', 'Predefined': False, 'PredefinedDataName': '', 'Parent@navigationLinkUrl': "Catalog_СтатьиЗатрат(guid'33ed0839-9697-11eb-8568-18c04d0357e4')/Parent"}}]}

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

Comments

[Модератор]

Скриншот фрагмента кода удалён модератором.
Фрагменты кода надо размещать в виде текста и оборачивать тэгом code для корректного отображения. Удобно делать кнопкой </>
Это обязательно, см.п.3.8 Регламента.
Сюда же относится traceback, ввод и вывод в консоли и другая структурированная текстовая инфа.

[Влад Григорьев]

вероятно надо использовать не append а extend

Ну и приведите пример входных данных и выходных, кто ж вам из скриншота что-то вытаскивать будет

ну и понятие нормальное дерево тоже - стоит расписать

[alexandrsemen4ukk]

Влад Григорьев, исправил, единственное входные данные кусочком.

[Влад Григорьев]

alexandrsemen4ukk, только добавьте не что получилось, а что хотите.

[shurshur]

Не очень понимаю в чём проблема. Данные можно преобразовать в словарь, где Ref_Key будет ключом:

data_dict = dict((x["Ref_Key"], x) for x in data)

После этого можно пройтись по элементам и добавить в каждый словарь родительский элемент ссылки. И рекурсия тут не нужна.

roots = []

for ref_key, item in data_dict.items():
    parent_key = item.get("Parent_Key", None)
    parent_item = data_dict.get(parent_key, None)

    # ссылка в никуда, видимо такого быть не должно, но
    # можно форсировать превращение item в корневой элемент
    #if parent_item is None:
    #    parent_key = None

    if parent_key is None: # родителя нет - это корень
        roots.append(item)
        continue

    if "childs" not in parent_item: parent_item["childs"] = []
    parent_item["childs"].append(item)

В итоге получаем в roots все корневые вершины, от которых растут все остальные через поле childs. IsFolder не пригодилось.

[alexandrsemen4ukk]

shurshur,

for ref_key, item in dictionaryList.items():
AttributeError: 'list' object has no attribute 'items'

в случае с вашим примером.

for ref_key, item in dictionaryList.items():
AttributeError: 'tuple' object has no attribute 'items'

- в случае если я список словарей на кортеж словарей, или словарь словарей соответственно

[shurshur]

alexandrsemen4ukk, дык в моём примере data_dict это dict, а не list и не tuple.

[alexandrsemen4ukk]

shurshur, а что за строка "childs" в условии

if "childs" not in parent_item: parent_item["childs"] = []

не понимаю на что его заменить, чтобы работало)

[shurshur]

alexandrsemen4ukk, в исходных данных каждая запись это словарь, в котором несколько ключей. Я добавляю в него ключ childs, в значении которого будет храниться список дочерних элементов. В следующей строчке делается append в childs, но parent_item["childs"] должен быть создан до первого вызова этого append.

Answer 1

[Алексей Черемисин]

Самое простое - преобразовать ваши данные в словарь (dict), где ключом будет являться Ref_Key (это я так понимаю, универсальный идентификатор объекта). Ну а уже по ключам можно бегать как угодно.
Ну и данные у вас не читаются!

>>> import json
>>> f = open('t.json')
>>> j = json.load(f)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python3.10/json/__init__.py", line 293, in load
    return loads(fp.read(),
  File "/usr/lib/python3.10/json/__init__.py", line 346, in loads
    return _default_decoder.decode(s)
  File "/usr/lib/python3.10/json/decoder.py", line 337, in decode
    obj, end = self.raw_decode(s, idx=_w(s, 0).end())
  File "/usr/lib/python3.10/json/decoder.py", line 353, in raw_decode
    obj, end = self.scan_once(s, idx)
json.decoder.JSONDecodeError: Expecting property name enclosed in double quotes: line 1 column 2 (char 1)
>>>

Comments

[alexandrsemen4ukk]

Потому что это не json, это уже преобразованный json. Забыл квадратные скобки добавить, чтобы это был список словарей. Сейчас исправлю.

Все дело в том, что я так и делаю. Но данные могут иметь вложенность, которую можно понять только по parent_key, а она указывает только на родителя, то есть если элемен лежит в 5 подпапках, то нужно узнать его родителя, потом родителя этого родителя и так до самого верхнего элемента

[Алексей Черемисин]

data = {
    1: {"name": "A1", "isfolder": True},
    2: {"name": "A11", "parent": 1, "isfolder": True},
    3: {"name": "B1", "isfolder": True},
    4: {"name": "B11", "parent": 3, "isfolder": True},
    41: {"name": "B12", "parent": 3 },
    5: {"name": "B111", "parent": 4 , "isfolder": True},
    6: {"name": "B112", "parent": 4 },
    7: {"name": "C1", "isfolder": True},
}

def ancestors(data, accum, id):
    accum.append(id)
    if data[id].get("parent", False):
        ancestors(data, accum, data[id].get("parent"))
    return accum #.append(id)


anc = ancestors(data, [], 5).reverse()
print(anc)

Вывод
[3, 4, 5]

Answer 2

[Влад Григорьев]

Если правильно понял то никакой рекурсии не надо.
но если нужна какая доп группировка то да возможно потребуется

from collections import defaultdict
from pprint import pprint
 <spoiler title="values">
d =[{'Ref_Key': '33ed0832-9697-11eb-8568-18c04d0357e4', 'DataVersion': 'AAABRgAAAAA=', 'DeletionMark': False,
      'Parent_Key': 'a888a6c7-bb96-11ea-834d-f0795994df35', 'IsFolder': True, 'Code': 'СГ-000359',
      'Description': '1.1. Затраты на приобретение прав на ЗУ ', 'ВидДеятельностиДляНалоговогоУчетаЗатрат': None,
      'ВидРасходовНУ': None, 'РеквизитДопУпорядочивания': '12', 'Код_Добавленный': '', 'Синтека_projectId': '',
      'Predefined': False, 'PredefinedDataName': '',
      'Parent@navigationLinkUrl': "Catalog_СтатьиЗатрат(guid'33ed0832-9697-11eb-8568-18c04d0357e4')/Parent"},
     {'Ref_Key': '33ed0834-9697-11eb-8568-18c04d0357e4', 'DataVersion': 'AAABSAAAAAA=', 'DeletionMark': False,
      'Parent_Key': 'a888a6c7-bb96-11ea-834d-f0795994df35', 'IsFolder': True, 'Code': 'СГ-000361',
      'Description': '1.5. Затраты на аренду ЗУ ', 'ВидДеятельностиДляНалоговогоУчетаЗатрат': None,
      'ВидРасходовНУ': None, 'РеквизитДопУпорядочивания': '13', 'Код_Добавленный': '', 'Синтека_projectId': '',
      'Predefined': False, 'PredefinedDataName': '',
      'Parent@navigationLinkUrl': "Catalog_СтатьиЗатрат(guid'33ed0834-9697-11eb-8568-18c04d0357e4')/Parent"},
     {'Ref_Key': '33ed0836-9697-11eb-8568-18c04d0357e4', 'DataVersion': 'AAABSgAAAAA=', 'DeletionMark': False,
      'Parent_Key': 'a888a6c7-bb96-11ea-834d-f0795994df35', 'IsFolder': True, 'Code': 'СГ-000363',
      'Description': '1.6. Затраты на изменение ВРИ.Проектирование', 'ВидДеятельностиДляНалоговогоУчетаЗатрат': None,
      'ВидРасходовНУ': None, 'РеквизитДопУпорядочивания': '14', 'Код_Добавленный': '', 'Синтека_projectId': '',
      'Predefined': False, 'PredefinedDataName': '',
      'Parent@navigationLinkUrl': "Catalog_СтатьиЗатрат(guid'33ed0836-9697-11eb-8568-18c04d0357e4')/Parent"},
     {'Ref_Key': '33ed0838-9697-11eb-8568-18c04d0357e4', 'DataVersion': 'AAABTAAAAAA=', 'DeletionMark': False,
      'Parent_Key': 'a888a6c7-bb96-11ea-834d-f0795994df35', 'IsFolder': True, 'Code': 'СГ-000365',
      'Description': '1.8. Прочие затраты на улучшения и содержание ЗУ',
      'ВидДеятельностиДляНалоговогоУчетаЗатрат': None, 'ВидРасходовНУ': None, 'РеквизитДопУпорядочивания': '15',
      'Код_Добавленный': '', 'Синтека_projectId': '', 'Predefined': False, 'PredefinedDataName': '',
      'Parent@navigationLinkUrl': "Catalog_СтатьиЗатрат(guid'33ed0838-9697-11eb-8568-18c04d0357e4')/Parent"}]</spoiler>

tree = defaultdict(list)

for value in d:
    tree[value['Parent_Key']].append(value)

pprint(tree)