如果找到，则执行循环并打印结果，否则再次执行循环：如何在Python中消除多个嵌套

Question

我有一本字典，包含以下结构的数千个元素：

    full_dict={'A': ['B','C','D','E'],
     'B':['A','C','D','E','F','X']
     'X':['W','Y','Z','S'],
     'S':['W','K','T'],
    ...}

每个字母都是一个单词。 每个单词都可以是另一个dict元素的键和值（与其他单词一起）

我试图找到一条从一个词到另一个词的“路径”。例如，从“a”到“S”的路径是a-B-X-S，因为S位于X、B中的X和a中的B的值之间

目前，我正在使用以下代码：

    query=['A','S']
    if 'S' in full_dict['A']:
        print ('Found during 1st iteration')
    else:
        for i in full_dict['A']:
            if 'S' in full_dict[i]:
                print ('Found during 2nd iteration')
            else:
                for ii in full_dict[i]:
                etc.

我做了10次迭代，效果很好，但我想知道是否有更好的方法。 先谢谢你

Answer 1

您可以将其设置为递归函数：

def findLink(path,target,links):
    if not isinstance(path,list): path = [path] # start path with initial word
    for linked in links.get(path[-1],[]):       # go through links of word
        if linked == target: return path+[target] # done, return full path
        if linked in path: continue               # avoid circular linking
        foundPath = findLink(path+[linked], target,links) # dig deeper
        if foundPath: return foundPath            # reached end on that path

输出：

full_dict={'A': ['B','C','D','E'],
     'B':['A','C','D','E','F','X'],
     'X':['W','Y','Z','S'],
     'S':['W','K','T'] }

print(findLink('A','S',full_dict))
['A', 'B', 'X', 'S'] 

Answer 2

您可以使用networkx包：

import networkx as nx
full_dict={'A': ['B','C','D','E'],
           'B': ['A','C','D','E','F','X'],
           'X': ['W','Y','Z','S'],
           'S': ['W','K','T'],
           }

g = nx.DiGraph() # directed graph
for k, v in full_dict.items():
    g.add_edges_from((k, to) for to in v)

print(*nx.all_simple_paths(g, 'A', 'S')) # ['A', 'B', 'X', 'S']

一个（嵌套的）循环通常不起作用，因为它最多会涉及很多嵌套，最坏的情况是，我们通常不知道需要多少嵌套

因此，可以考虑使用递归。但这可能会很复杂，因为您可能需要在打破潜在无限循环或记住中间结果（以减少计算）等方面投入大量精力

因此，在我看来，最好的方法是一个可以利用数据的图形结构的包

Answer 3

如果您这样做是为了生产，并且需要高性能、优化、所有可能的路径等，那么外部lib非常有用

如果您将此作为练习或其他可以确保干净输入（单词列表中没有循环）或不希望仅为一个操作使用外部库的操作，那么您可以尝试递归：

full_dict = {
     'A': ['B','C','D','E'],
     'B': ['A','C','D','E','F','X'],
     'X': ['W','Y','Z','S'],
     'S': ['W','K','T'],
}

def find_path(source, target):
     for key, words in full_dict.items():
          if target in words:
               yield target
               if key == source:  # check if it's source
                    yield source
               else:
                    # otherwise, look for this key as new target
                    yield from find_path(source, key)
               break  # prevent further checking of remaining items

用法：

list(find_key('A', 'S'))
# ['S', 'X', 'B', 'A']

# get it in the right order, reverse it
list(find_key('A', 'S'))[::-1]
# ['A', 'B', 'X', 'S']

该方法在单词列表中查找目标单词，然后生成每个键。而不是检查源代码中每个单词可能出现的单词列表，因为这会创建许多可能到达或可能无法到达目标的链

有关^{} expressions的详细信息

请注意Python3's recursion limit默认为1000。因此，如果单词链可能更长，请增加限制或使用其他方法。将限制设置为4并使用此修改的dictfull_dict = {'A': ['B', 'D', 'E'], 'B': ['A', 'D', 'E', 'F', 'X'], 'X': ['W', 'Y', 'Z', 'C'], 'C': ['W', 'K', 'T', 'S'], 'S': []}，您已经达到了A到S的限制，它现在是一个5的链（['A', 'B', 'X', 'C', 'S']）