Recursive search in python

Question

I am trying to implement a search algorithm in such a scenario: Assume there are 5 people: people # 0-4, people only know who directly works under them. For example, people 0 and 1 manage no one, people 2 manages people 0, people 3 manages people 1, while people 4 manages both people 2 and 3.

Assume I store this hierarchy in a list called hierarchyhierarchy = [[],[],[0],[1],[2,3]]

What I am trying to find is who works directly and indirectly under an arbitrary person, In this case, people who work directly and indirectly under 4 should be 0,1,2,3, or [0,1,2,3] = allUnder(hierarchy,ID = 4).

I think the solution to the question is some kind of recursive search, but I am quite fuzzy about recursion. The algorithm I am looking for should also be efficient in case of duplicate values (e.g. assume 3 manages both 0,1, the answer should still be 0,1,2,3).

I know I am supposed to put my solution first, but I really don't know how to solve it at this point... Any help will be greatly appreciated.

Update: I am also very interested in finding all direct and indirect manegement of a particular person.

Answer 1

Solution

Given that you want two-way search (ie to be able to search for both subordinates and managers), you'll want some kind of tree structure that encodes two-way links between its nodes. Here's a class that implements such a tree:

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

Testing it out

Here's how to use the above defined Tree class to solve your specified problem:

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

This is a classic CS chestnut that doesn't seem to get much exposure in modern coding tutorials (I think because many of the problems that used to be solved with trees now have simpler hash table/dict based answers).