Python-сообщество

misterMinister · Сен. 7, 2021 00:17:28

Здравствуйте. Помоги пожалуйста закончить рекурсию. Есть список словарей. Каждый словарь может иметь дочерние элементы и каждый дочерний элемент может иметь свои дочерние элементы. Этот список похож на список в формате JSON. Вот примерный список:

 list=[
	{
		"id": 1,
		"parent": 0,
		"children": [
			{
				"id": 3,
				"parent": 1,
				"children": [
					{
						"id": 6,
						"parent": 3,
						"children": []
					}
				]
			},
			{
				"id": 4,
				"parent": 1,
				"children": []
			},
			{
				"id": 5,
				"parent": 1,
				"children": []
			},
		]
	},
	{
		"id": 2,
		"parent": 0,
		"children": [
			{
				"id": 7,
				"parent": 2,
				"children": [
					{
						"id": 8,
						"parent": 7,
						"children": [
							{
								"id": 9,
								"parent": 8,
								"children": []
							},
							{
								"id": 10,
								"parent": 8,
								"children": []
							}
						]
					}
				]
			}
		]
	}
]
#А вот функция:
    def flatten(list,i):
        elementList.append('\t'.join([str(list[i]['id']), str(list[i]['parent'])]) + '\n')
        if list[i]['children']:
            flatten(list[i]['children'],i)
        return
flatten(list,0)

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

Отредактировано misterMinister (Сен. 7, 2021 21:10:53)

PEHDOM · Сен. 7, 2021 12:16:43

использвать list в качестве имени переменной плохая идея, ровно как и использвания любых ключевых слов или builtin типов/функций

Вот тут,

 flatten(list[i]['children'],i)

как мнекажеться, вам нужно передавать не і а 0.
И у вас отсутвует перебор элеметов списка.

==============================
Помещайте код в теги:

[code python][/code]

Бериегите свое и чужое время.

Отредактировано PEHDOM (Сен. 7, 2021 12:21:32)

py.user.next · Сен. 7, 2021 18:55:21

misterMinister
Помоги пожалуйста закончить рекурсию.

Сформулируй задачу. Нет такой задачи “закончить рекурсию”, потому что это может означать что угодно.

misterMinister
Моя функция проходит по первому объекту включая дочернии, потом начинает прыгать.

А нужно, чтобы она делала что? Это мы должны догадаться типа.

misterMinister · Сен. 7, 2021 21:08:10

PEHDOM
И у вас отсутвует перебор элеметов списка.

Вот он-то мне и нужен. Я не понимаю что надо передать в функцию и когда ее вызывать

py.user.next
Сформулируй задачу. Нет такой задачи “закончить рекурсию”, потому что это может означать что угодно.

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

 {id:1,parent:0,children:[]}

id - номер узла
parent - id родового узла, под которым должен находиться дочерний элемент
children - список дочерних элементов
Задача такая: написать функцию, которая пройдет по всем узлам (или словарям в списке) и выведет их в список со строками. То есть, было так:

 {
		"id": 1,
		"parent": 0,
		"children": [
			{
				"id": 3,
				"parent": 1,
				"children": [
					{
						"id": 6,
						"parent": 3,
						"children": []
					}
				]
			},
			{
				"id": 4,
				"parent": 1,
				"children": []
			},
			{
				"id": 5,
				"parent": 1,
				"children": []
			},
		]
	},

А стало так:

 [
 ['id','parent'],
 ['1','0'],
 ['3','1'],
 ['6','3'],
 ['4','1'],
 ['5','1']
]

Функция которая у меня есть сейчас выводит только первый узел и его дочерние элементы.

 ['id','parent'],
 ['1','0'],
 ['3','1'],
 ['6','3']
]

А дальше либо не проходит, либо прыгает по списку.

PEHDOM · Сен. 8, 2021 11:53:13

 lst=[
	{
		"id": 1,
		"parent": 0,
		"children": [
....
]	
def flatten(lst):
    for item in lst:
        print('\t'.join([str(item['id']), str(item['parent'])]))
        if item['children']:
            flatten(item['children'])
flatten(lst)
>>> 
1	0
3	1
6	3
4	1
5	1
2	0
7	2
8	7
9	8
10	8
>>>

==============================
Помещайте код в теги:

[code python][/code]

Бериегите свое и чужое время.

Отредактировано PEHDOM (Сен. 8, 2021 15:09:46)

py.user.next · Сен. 8, 2021 19:09:15

  
>>> def f(dct, acc):
...     kid = str(dct['id'])
...     kparent = str(dct['parent'])
...     acc.append([kid, kparent])
...     for i in dct['children']:
...         acc = f(i, acc)
...     return acc
... 
>>> dct = {
...     'id': 1,
...     'parent': 0,
...     'children': [
...     {
...         'id': 3,
...         'parent': 1,
...         'children': [
...             {
...                 'id': 6,
...                 'parent': 3,
...                 'children': []
...             }
...         ]
...     },
...     {
...         'id': 4,
...         'parent': 1,
...         'children': []
...     },
...     {
...         'id': 5,
...         'parent': 1,
...         'children': []
...     }
...     ]
... }
>>> 
>>> out = f(dct, [])
>>> out
[['1', '0'], ['3', '1'], ['6', '3'], ['4', '1'], ['5', '1']]
>>>
>>> out1 = f(dct, [])
>>> out1
[['1', '0'], ['3', '1'], ['6', '3'], ['4', '1'], ['5', '1']]
>>> 
>>> out2 = f(dct, [])
>>> out2
[['1', '0'], ['3', '1'], ['6', '3'], ['4', '1'], ['5', '1']]
>>>

Для добавки id и parent в начале делаешь вторую функцию, которая вставляет id и parent, а потом использует рекурсивную функцию для собирания пар.

И сделать

  
def f(dct, acc=[]):
 
...
 
out = f(dct)

будет неправильно, так как в питоне этот объект будет висеть после вызова функции и следующий вызов этой же функции будет использовать уже заполненный список.
Вот что получается, если так сделать

  
>>> def f(dct, acc=[]):
...     kid = str(dct['id'])
...     kparent = str(dct['parent'])
...     acc.append([kid, kparent])
...     for i in dct['children']:
...         acc = f(i, acc)
...     return acc
... 
>>> dct = {
...     'id': 1,
...     'parent': 0,
...     'children': [
...     {
...         'id': 3,
...         'parent': 1,
...         'children': [
...             {
...                 'id': 6,
...                 'parent': 3,
...                 'children': []
...             }
...         ]
...     },
...     {
...         'id': 4,
...         'parent': 1,
...         'children': []
...     },
...     {
...         'id': 5,
...         'parent': 1,
...         'children': []
...     }
...     ]
... }
>>> 
>>> out = f(dct)
>>> out
[['1', '0'], ['3', '1'], ['6', '3'], ['4', '1'], ['5', '1']]
>>> 
>>> out1 = f(dct)
>>> out1
[['1', '0'], ['3', '1'], ['6', '3'], ['4', '1'], ['5', '1'], ['1', '0'], ['3', '1'], ['6', '3'], ['4', '1'], ['5', '1']]
>>> 
>>> out2 = f(dct)
>>> out2
[['1', '0'], ['3', '1'], ['6', '3'], ['4', '1'], ['5', '1'], ['1', '0'], ['3', '1'], ['6', '3'], ['4', '1'], ['5', '1'], ['1', '0'], ['3', '1'], ['6', '3'], ['4', '1'], ['5', '1']]
>>>

Отредактировано py.user.next (Сен. 9, 2021 00:46:43)

misterMinister · Сен. 13, 2021 23:54:27

Спасибо всем еще раз. Я сам позже нашел решение, в точности такое же как и у PEHDOM

Python-сообщество

Уведомления

#1 Сен. 7, 2021 00:17:28

Рекурсивная функция для листа

#2 Сен. 7, 2021 12:16:43

Рекурсивная функция для листа

#3 Сен. 7, 2021 18:55:21

Рекурсивная функция для листа

#4 Сен. 7, 2021 21:08:10

Рекурсивная функция для листа

#5 Сен. 8, 2021 11:53:13

Рекурсивная функция для листа

#6 Сен. 8, 2021 19:09:15

Рекурсивная функция для листа

#7 Сен. 13, 2021 23:54:27

Рекурсивная функция для листа

Board footer