时间戳

首页 > 解决方案 > Python：使用递归通过列表查找路径

python - Python：使用递归通过列表查找路径

问题描述

使用 python 我试图弄清楚如何找到从列表中的一个数字到另一个列表中的数字的“路线”。

例如，如果我有列表：

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

从 1 到 10 的路线将是 A -> B -> C，因为 4 在 A 和 B 中，而 7 在 B 和 C 中。我试图弄清楚如何找到并记录从一个值到另一个问题是列表数量更多且元素更多的问题，其中并非每个列表都共享理想的公共元素。我想我需要使用递归，但似乎无法提出解决方案。任何帮助将不胜感激。

标签： pythonlistloopsrecursionmath

解决方案

您可以将递归与生成器一起使用：

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']

推荐阅读