Как получить путь до id в объекте?

Question

[pcdesign]

Есть вот такая структура

[
    {
        "parent_id":None,
        "sub_cats":[
            {
                "parent_id":472,
                "descr":"D",
                "level":1,
                "id":508,
                "order":0,
                "sub_cats":[
                    {
                        "parent_id":472,
                        "sub_cats":[
                            {
                                "parent_id":508,
                                "sub_cats":[

                                ],
                                "descr":"FOO",
                                "level":2,
                                "id":1076,
                                "order":0
                            }
                        ],
                        "descr":"Bar",
                        "level":1,
                        "sub_cats_ids":[

                        ]
                    }
                ]
            },
            {
                "parent_id":472,
                "descr":"E",
                "level":1,
                "id":490,
                "order":1
            }
        ],
        "descr":"A",
        "level":0,
        "id":472,
        "order":0
    },
    {
        "parent_id":None,
        "sub_cats":[

        ],
        "descr":"B",
        "level":0,
        "id":544,
        "order":1
    }
]

Все что я знаю это id.
Этот id может быть и в корне и в подразделах. Кол-во вложений произвольное.
Например, пришел id = 1076
Хотелось бы получить вот такой путь:

A > D > FOO

A, D, FOO - это атрибуты descr.

Comments

[pcdesign]

Алексей Аминодов-Борисов, нет. не просто descr. А всю цепочку от родителя и до подраздела где целевой id.

Answer 1

[Иван Клименко]

Рекурсивным обходом:

function getDescriptionChain(subCats, id) {
    for (const subCat of subCats) {
        if (subCat.id === id) {
            return [subCat.descr];
        } else {
            const chain = getDescriptionChain(subCat.sub_cats, id);
            if (chain.length > 0) {
                return [subCat.descr, ...chain];
            }
        }
    }
    return [];
}

Использование

const subCats = [
    {
        "parent_id": null,
        "sub_cats": [
            {
                "parent_id": 472,
                "descr": "D",
                "level": 1,
                "id": 508,
                "order": 0,
                "sub_cats": [
                    {
                        "parent_id": 472,
                        "sub_cats": [
                            {
                                "parent_id": 508,
                                "sub_cats": [
                                ],
                                "descr": "FOO",
                                "level": 2,
                                "id": 1076,
                                "order": 0
                            }
                        ],
                        "descr": "Bar",
                        "level": 1,
                        "id": 345,
                        "sub_cats_ids": [
                        ]
                    }
                ]
            },
            {
                "parent_id": 472,
                "descr": "E",
                "level": 1,
                "id": 490,
                "order": 1
            }
        ],
        "descr": "A",
        "level": 0,
        "id": 472,
        "order": 0
    },
    {
        "parent_id": null,
        "sub_cats": [
        ],
        "descr": "B",
        "level": 0,
        "id": 544,
        "order": 1
    }
];

const chain = getDescriptionChain(subCats, 1076);
console.log(chain.join(' > ')); // "A > D > Bar > FOO"

Comments

[Ternick]

Идеально, тег стоит python, ответ на js :)

[Иван Клименко]

Ternick, и правда, проглядел. Теперь одна надежда на то, что автор не совсем новичок и суть поймёт

[Ternick]

Иван Клименко, Понять можно, но я в js не сильно много чего понимаю. Я попробую конвертировать в python.

[Иван Клименко]

Ternick, давайте, получится настоящая командная работа

[Ternick]

Иван Клименко, Всё, я сделал. У вас ответ кстати не очень правильный :)

[Иван Клименко]

Ternick, ответ правильный, нет никакой причины пропускать объект с "descr": "Bar".

Answer 2

[trester]

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

Comments

[pcdesign]

Да, я знаю как это решить обычным рекурсивным перебором.
Просто задал вопрос потому что думал есть более короткое решение, типа с помощью dpath или jmespath и т.д..

Answer 3

[Ternick]

КОД:

subCats = [
    {
        "parent_id":None,
        "sub_cats":[
            {
                "parent_id":472,
                "descr":"D",
                "level":1,
                "id":508,
                "order":0,
                "sub_cats":[
                    {
                        "parent_id":472,
                        "sub_cats":[
                            {
                                "parent_id":508,
                                "sub_cats":[

                                ],
                                "descr":"FOO",
                                "level":2,
                                "id":1076,
                                "order":0
                            }
                        ],
                        "descr":"Bar",
                        "level":1,
                        "sub_cats_ids":[

                        ]
                    }
                ]
            },
            {
                "parent_id":472,
                "descr":"E",
                "level":1,
                "id":490,
                "order":1
            }
        ],
        "descr":"A",
        "level":0,
        "id":472,
        "order":0
    },
    {
        "parent_id":None,
        "sub_cats":[

        ],
        "descr":"B",
        "level":0,
        "id":544,
        "order":1
    }
]

def isKeyInDict(d, key):
	try:
		d[key]
		return True
	except Exception:
		return False

def getDescriptionChain(subCats, id):
	for subCat in subCats:
		if isKeyInDict(subCat["sub_cats"][0], "id"):
			if subCat["sub_cats"][0]["id"] == id:
				return [subCat["sub_cats"][0]["descr"]]
			else:
				chain = getDescriptionChain(subCat["sub_cats"], id)
				if len(chain) > 0:
					return [subCat["descr"]] + chain
		else:
			chain = getDescriptionChain(subCat["sub_cats"], id)
			if len(chain) > 0:
				return [subCat["descr"]] + chain
	return []

if __name__ == '__main__':
	print(" > ".join(getDescriptionChain(subCats, 1076)))

Выводит это:
A > D > FOO

Comments

[Ternick]

Не работает.

[Иван Клименко]

Ternick, а вот так?)

def getDescriptionChain(subCats, id):
	for subCat in subCats:
		if subCat["id"] == id:
			return [subCat["descr"]]
		else:
			chain = getDescriptionChain(subCat["sub_cats"], id)
			if len(chain) > 0:
				return [subCat["descr"]] + chain
	return []

Использование

import json

subCatsRaw = """
[
    {
        "parent_id": null,
        "sub_cats": [
            {
                "parent_id": 472,
                "descr": "D",
                "level": 1,
                "id": 508,
                "order": 0,
                "sub_cats": [
                    {
                        "parent_id": 472,
                        "sub_cats": [
                            {
                                "parent_id": 508,
                                "sub_cats": [
                                ],
                                "descr": "FOO",
                                "level": 2,
                                "id": 1076,
                                "order": 0
                            }
                        ],
                        "descr": "Bar",
                        "level": 1,
                        "id": 345,
                        "sub_cats_ids": [
                        ]
                    }
                ]
            },
            {
                "parent_id": 472,
                "descr": "E",
                "level": 1,
                "id": 490,
                "order": 1
            }
        ],
        "descr": "A",
        "level": 0,
        "id": 472,
        "order": 0
    },
    {
        "parent_id": null,
        "sub_cats": [
        ],
        "descr": "B",
        "level": 0,
        "id": 544,
        "order": 1
    }
]
"""

subCats = json.loads(subCatsRaw)
print(" > ".join(getDescriptionChain(subCats, 1076))) # A > D > Bar > FOO

[Ternick]

Иван Клименко, моё решение работает, но если взять другой ключ оно ругается на то что в одном субкате нету пути дальше. Автору нужно более простое решение, не через рекурсию

[Иван Клименко]

Ternick, такую задачу нельзя решить не через рекурсию

[Ternick]

Иван Клименко, посмотрите комент к первому ответу

[Иван Клименко]

Ternick, ну действительность не обязана сходится с желаниями автора. А действительность в том, что решить такую задачу можно только рекурсивно