LINUX.ORG.RU
Форум — Development  

Работа со словарем древовидной структуры

 , ,


0

2

Есть словарь вида: 

{
	1: {'name': 'Земля', 'parent': None}, 
	2: {'name': 'Евразия': 'parent': 1},
	3: {'name': 'Китай': 'parent': 2}, 
	4: {'name': 'Пекин': 'parent': 3},
	5: {'name': 'Австралия': 'parent': 1},  
	6: {'name': 'Сидней': 'parent': 5}
}

Нужно по ключу элемента получить всех родителей, например для ключа 4 - нужно получить элементы Китай, Евразия, Земля для ключа 6 - нужно получить элементы Австралия, Земля

Погуглил нашел, что-то похожее с использованием treelib, хочется сделать без сторонних библиотек, с первого взгляда задача несложная

← Xterm в Tk. Почему не каждый цветной терминальный вывод отображается через Popen+communicate?
Django TIME_ZONE queryset →

хочется сделать без сторонних библиотек

Если хочется, то делайте, ни в чем себе не отказывайте)

с первого взгляда задача несложная

Задача реально простая.

goingUp ★★★★★
()

Можно воспроизвести тот же самый поиск, что производится человеком.

Можно преобразовать структуру таким образом,чтобы в ней можно было проще искать.

Можно составить какую-нибудь таблицу для поиска (а-ля второй вариант, но облегчённый).

Короче, вариантов много.

Но если было принято решение отказаться от библиотеки и запилить собственное решение, в этом есть какой-то смысл?

Hanuken ★
()

Псс, дружище, не хочешь немного рекурсии?

tree = {
    1: {'name': 'Земля', 'parent': None},
    2: {'name': 'Евразия', 'parent': 1},
    3: {'name': 'Китай', 'parent': 2},
    4: {'name': 'Пекин', 'parent': 3},
    5: {'name': 'Австралия', 'parent': 1},
    6: {'name': 'Сидней', 'parent': 5}
}

def path(tree, id):
    """Returns a stringified sequence of node names along a path 
    in the 'tree' from a node with 'id' to a root node."""
    if tree[id]['parent'] == None:
        return tree[id]['name']
    else:
        return ', '.join([tree[id]['name'], path(tree, tree[id]['parent'])])


path(tree, 4) # 'Пекин, Китай, Евразия, Земля'
Nervous ★★★★★
()
Последнее исправление: Nervous (всего исправлений: 3)
Ответ на: комментарий от snizovtsev

Мне кажется ChatGPT должен справиться.

У кого там есть доступ, внесите вариант от чатгопоты, вместе с промптом. Поглядим, на что годится его сияющая металлическая задница.

Nervous ★★★★★
()
Ответ на: комментарий от Nervous

ChatGPT

def get_parents(d, key):
    item = d[key]
    parents = []
    while item['parent']:
        parent = d[item['parent']]
        parents.append(parent['name'])
        item = parent
    parents.append(item['name'])
    return parents[::-1]

# Пример использования
d = {
    1: {'name': 'Земля', 'parent': None},
    2: {'name': 'Евразия', 'parent': 1},
    3: {'name': 'Китай', 'parent': 2},
    4: {'name': 'Пекин', 'parent': 3},
    5: {'name': 'Австралия', 'parent': 1},
    6: {'name': 'Сидней', 'parent': 5}
}

print(get_parents(d, 4))  # ['Земля', 'Евразия', 'Китай', 'Пекин']
print(get_parents(d, 6))  # ['Земля', 'Австралия', 'Сидней']
vvn_black ★★★★★
()
Ответ на: комментарий от Nervous

Вот что отвечает ChatGPT (промпт: тупо копипаст сообщения ТС и просьба написать все на питоне)
=========================

Можно реализовать функцию, которая будет рекурсивно обходить словарь и добавлять всех родителей для заданного элемента. Вот код:

```
def get_parents(d, id):
    result = []
    if id in d:
        parent_id = d[id]['parent']
        if parent_id is not None:
            parent = d[parent_id]
            result.extend(get_parents(d, parent_id))
            result.append(parent['name'])
    return result
```


Эта функция принимает словарь и идентификатор элемента, для которого нужно получить всех родителей. Она начинает с проверки, есть ли такой элемент в словаре. Затем получает идентификатор родительского элемента и проверяет, указан ли он. Если родительский элемент есть, функция рекурсивно вызывает сама себя для этого элемента и добавляет результат в список. Затем функция добавляет имя родительского элемента в список и возвращает его.

Пример использования:

```
d = {
  1: {'name': 'Земля', 'parent': None},
  2: {'name': 'Евразия', 'parent': 1},
  3: {'name': 'Китай', 'parent': 2},
  4: {'name': 'Пекин', 'parent': 3},
  5: {'name': 'Австралия', 'parent': 1},
  6: {'name': 'Сидней', 'parent': 5}
}

print(get_parents(d, 4)) # ['Китай', 'Евразия', 'Земля']
print(get_parents(d, 6)) # ['Австралия', 'Земля']
```

anonymous_sapiens ★★★★★
()
Последнее исправление: anonymous_sapiens (всего исправлений: 2)
Ответ на: комментарий от Nervous

Зачем здесь рекурсия?

Пока parent не равно None; печатай имя и переходи к след. элементу по «указателю» parent

условный код

while item->parent != None {
  do-some-thing with name
  item=item->parent
}
futurama ★★★★★
()
Последнее исправление: futurama (всего исправлений: 1)

:D ⋆⁺₊⋆ ☾⋆⁺₊⋆

local dict =
{
    {name = 'Земля',    parent = nil},
    {name = 'Евразия',  parent = 1  },
    {name = 'Китай',    parent = 2  },
    {name = 'Пекин',    parent = 3  },
    {name = 'Австралия',parent = 1  },
    {name = 'Сидней',   parent = 5  }
};

function dict:get(id)
    while(self[id].parent) do
         id=self[id].parent;
         print(self[id].name);
    end
end

print("--------");
dict:get(4);
print("--------");
dict:get(6); 

dron@gnu:~$ lua lua.lua 
--------
Китай
Евразия
Земля
--------
Австралия
Земля
dron@gnu:~$
LINUX-ORG-RU ★★★★★
()
Последнее исправление: LINUX-ORG-RU (всего исправлений: 2)
Ответ на: комментарий от Norgat

в [тут хотел матом выругаться чтобы было созвучно с ширину]:

def get_parents(d: dict, k: int) -> list[str]:
    return (
        [] if d[k]["parent"] is None else get_parents(d, d[k]["parent"])
    ) + [d[k]["name"]]


d = {
    1: {"name": "Земля", "parent": None},
    2: {"name": "Евразия", "parent": 1},
    3: {"name": "Китай", "parent": 2},
    4: {"name": "Пекин", "parent": 3},
    5: {"name": "Австралия", "parent": 1},
    6: {"name": "Сидней", "parent": 5},
}


print(*get_parents(d, 4), sep=" -> ")
# Земля -> Евразия -> Китай -> Пекин
uwuwuu
()
Последнее исправление: uwuwuu (всего исправлений: 1)
Ответ на: комментарий от Norgat

Он у себя на сайте breadcrumbs выводит. Как тут Форум — Development. Их вложенность ограничена 3-4 уровнями обычно, а не 1000. Странно, что человек, который у себя в навыках указал vue.js сразу не догадался

uwuwuu
()
Последнее исправление: uwuwuu (всего исправлений: 1)
Ответ на: комментарий от uwuwuu

Хлебные крошки за меня давно другие люди пишут) На такие вещи смотрю в разрезе - а что будет если человек по неопытности засунет этот код в нагрузку?

Norgat ★★★★★
()
← Xterm в Tk. Почему не каждый цветной терминальный вывод отображается через Popen+communicate?
Development
Django TIME_ZONE queryset →