遍历数组以查找最高配对

Question

假设我有一个数组，其中包含子元素（作为每个数组的第0个元素）和父元素（作为每个数组的第1个元素），如下所示：

[[child, parent], [child, parent], [child, parent]]

下面是一个真实的例子：

[[Mary, Dan], [Dan, Steven], [Steven, Craig], [Janice, Keith]]

玛丽是丹的孩子，丹是史蒂文的孩子，史蒂文是克雷格的孩子。珍妮丝和基思与这个家庭没有联系。每个孩子只有一个父母。此外，配对代表了家庭中所有可能的配对。由于Janice和Keith都不在这个家庭的任何其他子女/父母配对中，我们知道他们没有联系

既然Mary是输入，那么我如何创建一个循环来返回Craig作为Mary的最早祖先呢

我在想一个while循环，它以Mary作为输入，然后以Dan开始循环，然后以Steven开始循环，然后以Craig开始循环，然后在没有找到匹配项时，返回Craig。然而，我希望它能在理论上无限长的祖先身上工作。我觉得这应该很简单，但我还没有找到一个可行的解决方案，除了在彼此之间编写一堆for循环，而这些循环在100个祖先的列表上是行不通的

Answer 1

您可以从数组中创建字典（子级到父级），并使用while循环方法：

data = [['Mary', 'Dan'], ['Dan', 'Steven'], ['Steven', 'Craig'], ['Janice', 'Keith']]
tree = {child: parent for child, parent in data}

def oldest_ancestor(child):
    parent = child
    while tree.get(parent, None) is not None:
        parent = tree[parent]
    return parent

print(oldest_ancestor('Mary')) # Craig

Answer 2

你可以这样做：

data = [['Mary', 'Dan'], ['Dan', 'Steven'], ['Steven', 'Craig'], ['Janice', 'Keith']]


def get_oldest_ancestor(d, source):
    def getParent(d, source):
        return next((parent for child, parent in d if child == source), None)

    while True:
        parent = getParent(d, source)
        if parent:
            source = parent
        else:
            return source


ancestor = get_oldest_ancestor(data, 'Mary')
print(ancestor)

输出

Craig

Answer 3

你需要把孩子的父母和其他孩子进行比较，看他们是否存在

family = [["Mary", "Dan"], ["Dan", "Steven"], ["Steven", "Craig"],["Janice", "Keith"]]



def oldestAncestor(child):
    directParent = ""
    for pair in family:
        if pair[0] == child:
            directParent = pair[1]
            pass
        if directParent == pair[0]:
            directParent = pair[1]
            pass
        pass
    return directParent

print (oldestAncestor("Mary"))

回答

Craig