Python：使用递归在列表中查找路径

Question

使用python，我试图找出如何从一个列表中的一个数字到另一个列表中的一个数字的“路由”。你知道吗

例如，如果我有以下列表：

A = [1,2,3,4]
B = [4,5,6,7]
C = [7,8,9,10]

从1到10的路径将是A->；B->；C，因为A和B中有4个，B和C中有7个。我正在尝试找出如何查找和记录从一个值到另一个值的路径，以解决一个问题，即列表的数量要大得多，元素也多，而不是每个列表都共享理想的公共元素。我想我需要使用递归，但似乎不能想出一个解决方案。如有任何帮助，我们将不胜感激。你知道吗

Answer 1

可以对生成器使用递归：

d = {'A': [1, 2, 3, 4], 'B': [4, 5, 6, 7], 'C': [7, 8, 9, 10]}
def find_path(start, end, c = [], seen = []):
   _r = [a for a, b in d.items() if any(i in b for i in d[start]) and a not in seen]
   if end in _r:
      yield c+[end]
   else:
      for i in _r:
        yield from find_path(i, end, c = c+[i], seen=seen+[start])


print(min(find_path('A', 'C', c = ['A']), key=len))

输出：

['A', 'B', 'C']

这将适用于较大的输入：

d = {'A': [1, 2, 3, 4], 'B': [4, 5, 6, 7], 'C': [7, 8, 9, 10], 'D':[30, 45, 23], 'F':[10, 11, 12, 13], 'G':[13, 14, 15]}
print(min(find_path('A', 'G', c = ['A'], seen=['A']), key=len))

输出：

['A', 'B', 'C', 'F', 'G']

Answer 2

如果你负担得起，我建议你采取以下方法

• 创建一个图，其中每个节点表示其中一个列表
• 对于每个列表中的每个数字，如果该数字存在于另一个列表中，则在节点之间创建一个连接
• 对于查询，（1）查找开始节点，（2）查找结束节点，以及（3）使用最短路径算法，例如从^{}