DjangoBB LoFi version

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

Начало » Центр помощи » Рекурсивная функция для листа

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)

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

PEHDOM

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

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

Вот тут,

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

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

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

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

misterMinister

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

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