Python: поиск пути по спискам с помощью рекурсии

Question

Используя 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. Я пытаюсь выяснить, как я подхожу к поиску и записипуть от одного значения к другому для проблемы с гораздо большим числом списков с большим количеством элементов, где не каждый список разделяет идеальные общие элементы. Я думаю, что мне нужно использовать рекурсию, но не могу найти решение. Любая помощь будет оценена заранее спасибо.

Answer 1

Если вы можете себе это позволить, я предлагаю следующий подход

• создать график, где каждый узел представляет один из этих списков
• для каждого числа в каждом списке, если это числоприсутствует в другом списке, создать соединение между узлами
• для запроса, (1) найти начальный узел, (2) найти конечный узел и (3) использовать алгоритм кратчайшего пути, например из networkX

Answer 2

Вы можете использовать рекурсию с генератором:

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