Рекурсивный поиск в питоне

Question

Я пытаюсь реализовать алгоритм поиска в таком сценарии: предположим, что есть 5 человек: люди № 0-4, люди знают только, кто непосредственно работает с ними.Например, люди 0 и 1 никому не управляют, люди 2 управляют людьми 0, люди 3 управляют людьми 1, а люди 4 управляют людьми 2 и 3.

Предположим, я храню эту иерархию в списке, называемом иерархией hierarchy = [[],[],[0],[1],[2,3]]

Я пытаюсь выяснить, кто работает прямо и косвенно под произвольным лицом. В данном случае это люди, которые работают прямо и косвенно.меньше 4 должно быть 0,1,2,3, или [0,1,2,3] = allUnder(hierarchy,ID = 4).

Я думаю, что решение вопроса - это какой-то рекурсивный поиск, но я не совсем понимаю рекурсию.Алгоритм, который я ищу, также должен быть эффективным в случае дублирования значений (например, предположим, что 3 управляет обоими значениями 0,1, ответ должен быть 0,1,2,3).

Я знаю, что я долженпоставить свое решение на первое место, но я действительно не знаю, как решить его на данный момент ... Любая помощь будет принята с благодарностью.

Обновление: я также очень заинтересован в поиске всех прямых и косвенных управленияконкретного человека.

Answer 1

Я представляю иерархию как словарь:

hierarchy = { 4: { 2: 0, 3: 1 } }

Где я могу определить рекурсивный метод для получения детей:

def get_all_children(father, res=None):
  if res == None: res = []
  res.extend(father.keys())
  for child in father.values():
    if not isinstance(child, dict):
      res.append(child)
    else: get_all_children(child, res)
  return res

Тогда я могу позвонить:

print(get_all_children(hierarchy[4]))
#=> [2, 3, 0, 1]

---

Также

hierarchy = {5: { 4: {2: 0, 3: 1} }, 8: {7: 6} }
print(get_all_children(hierarchy[5]))
#=> [4, 2, 3, 0, 1]

Answer 2

Решение

Учитывая, что вы хотите двусторонний поиск (то есть, чтобы иметь возможность искать как подчиненных, так и менеджеров), вам понадобится какая-то древовидная структура, которая кодирует двусторонние связи между его узлами,Вот класс, который реализует такое дерево:

class Node:
    def __init__(self, val):
        """initialize a node with the worker id value
        """
        self._children = []
        self._parent = None
        self.val = val

    def link(self, *node):
        """create a parent-child link between this (parent) node and one
        or more (children) nodes
        """
        for n in node:
            n._parent = self
            self._children.append(n)

    def get(self):
        """depth-first recursive get
        """
        return [x for y in ([n.val] + n.get() for n in self._children) for x in y]

    def getparents(self):
        """walks up parents (currently there's at most one parent per-node)
        """
        return [] if self._parent is None else [self._parent.val] + self._parent.getparents()

class Tree:
    def __init__(self, idlists):
        """initialize the tree as per the OP's example input
        """
        self._nodes = {}
        for topid,idlist in enumerate(idlists):
            self.add(topid, idlist)

    def __getitem__(self, key):
        return self._nodes[key]

    def _getnode(self, i):
        """get or create the node with id=i.
        Avoid constructing new Nodes if we don't have to 
        """
        if i in self._nodes:
            return self._nodes[i]
        else:
            n = self._nodes[i] = Node(i)
            return n

    def add(self, topid, idlist):
        """create a node with id=topid (if needed), then add
        child nodes, one per entry in idlist
        """
        self._getnode(topid).link(*(self._getnode(i) for i in idlist))

Проверка его

Вот как использовать определенный выше класс Tree для решения указанной проблемы:

data = [[],[],[0],[1],[2,3]]
people = Tree(data)

## get subordinates

print(people[4].get())
# output: [2, 0, 3, 1]
print(people[2].get())
# output: [0]
print(people[1].get())
# output: []

## get managers

print(people[1].getparents())
# output: [3, 4]
print(people[2].getparents())
# output: [4]
print(people[4].getparents())
# output: []

Ramble

Это классический CS-каштан, который, кажется, не получает особого внимания в современных уроках кодирования (я думаю, потому что многие из проблем, которые раньше решались с деревьями, теперь имеют более простую хэш-таблицу /основанные на диктате ответы).

Answer 3

Если предположить иерархию сверху вниз, этого достаточно:

people = [[],[],[0],[1],[2,3]]

def manages(manager, people):
  lst = people[manager]
  for employee in lst:
    lst = lst + manages(employee, people)
  return lst

print(set(manages(4, people)))

Выходы: {0, 1, 2, 3}

Вот рабочий пример .

Это решение не будет прекращено, если в списке ввода есть круговые отношения.

Answer 4

Представьте эту проблему как ориентированный граф, используя список смежности, такой как структура данных.И исходя из вашего предположения, 3 управляет 0 и 1.

graph = {4: [2, 3], 2: [0], 3: [0, 1]}

ИспользованиеОбратный поиск по глубине (DFS) или Breat-First-Search (BFS) для перечисления людей, которые сообщают о человеке.

DFS (график [2]) должен возвращать 0

DFS(график [4]) должен возвращать 0, 2, 1, 3

BFS (график [4]) должен возвращать 2, 3, 0, 1