Python字典递归搜索

Question

它的工作方式是键可以转换为与其相关联的列表中的任何值。所以我要回答的问题是 maximus 会变成 bumble。该函数应返回 True，因为 maximus -> bee -> bumble。

到目前为止，我的函数使用以下逻辑:

for i in transformers[start]:
    if i in transformers values:
        if desired in transformers[start]:
            return True
        else:
            return search(transformers, i,desired)

所以发生的事情是它通过第一个递归并说“好的，maximus 现在是质数。”但是在 prime 开始的第二次递归中，它从函数返回并且甚至不检查如果 maximus 变成蜜蜂会发生什么，因为一旦它遇到 OldPrime，它就什么也没有返回。

transformers = {
    "maximus" : ["prime", "bee", "bomber"],
    "prime" : ["oldPrime","youngerPrime"],
    "bee" : ["bumble","oldBumble"],
    "plareon" : ["moltrees"]
}

Answer 1

我们可以使用递归来做到这一点。递归总是有基本情况和归纳情况。

基本情况是:

"An object can transform into itself." (1)

归纳情况是:

"An object can transform into the requested object req given it can transform into a next object nxt and that object can transform into the requested object. (2)

你可以通过递归来做到这一点:

def can_transform(st, trans, req):
    if st == req:  # (1)
        return True
    else:  # (2)
        return any(can_transform(nxt, trans, req)
                   for nxt in trans.get(st, ()))

然而，上述方法存在一个潜在问题:我们可能会陷入无限循环。例如，如果转换字典如下所示:

{
  'A': ['B','C'],
  'B': ['A']
}

然后我们看'A'是否可以变成'C'，然后程序会搜索下面的路径:

'A' -> 'B' -> 'A' -> 'B' -> ...

所以我们永远不会寻找'C'。

我们可以通过维护一组我们已经访问过的元素来防止这种情况发生。

def can_transform(st, trans, req):
    visited = set()
    <b>def recurse(st):</b>
        if st == req:
            return True
        <b>elif st not in visited</b>:
            <b>visited.add(st)</b>
            return any(recurse(nxt)
                       for nxt in trans.get(st, ()))
        <b>return False</b>
    return recurse(st)

每次我们访问一个元素时，我们将其标记为已访问，这样我们就不能再访问它了。