Комбинации в пары

Question

Я работаю над направленной сетевой проблемой и пытаюсь вычислить все допустимые пути между двумя точками. Мне нужен способ взглянуть на пути до 30 «поездок» (обозначенных парой [origin, destination]) длиной. Полный маршрут затем состоит из ряда этих пар:

route = [[start, city2], [city2, city3], [city3, city4], [city4, city5], [city5, city6], [city6, city7], [city7, city8], [city8, stop]] 

До сих пор мое лучшее решение следующим образом:

def numRoutes(graph, start, stop, minStops, maxStops): 
    routes = [] 

    route = [[start, stop]] 
    if distance(graph, route) != "NO SUCH ROUTE" and len(route) >= minStops and len(route) <= maxStops: 
      routes.append(route) 

    if maxStops >= 2: 
     for city2 in routesFromCity(graph, start): 
      route = [[start, city2],[city2, stop]] 
      if distance(graph, route) != "NO SUCH ROUTE" and len(route) >= minStops and len(route) <= maxStops: 
       routes.append(route) 
    if maxStops >= 3:  
     for city2 in routesFromCity(graph, start): 
      for city3 in routesFromCity(graph, city2): 
       route = [[start, city2], [city2, city3], [city3, stop]] 
       if distance(graph, route) != "NO SUCH ROUTE" and len(route) >= minStops and len(route) <= maxStops: 
        routes.append(route) 

    if maxStops >= 4: 
     for city2 in routesFromCity(graph, start): 
      for city3 in routesFromCity(graph, city2): 
       for city4 in routesFromCity(graph, city3): 
        route = [[start, city2], [city2, city3], [city3, city4], [city4, stop]] 
        if distance(graph, route) != "NO SUCH ROUTE" and len(route) >= minStops and len(route) <= maxStops: 
         routes.append(route) 
    if maxStops >= 5: 
     for city2 in routesFromCity(graph, start): 
      for city3 in routesFromCity(graph, city2): 
       for city4 in routesFromCity(graph, city3): 
        for city5 in routesFromCity(graph, city4): 
         route = [[start, city2], [city2, city3], [city3, city4], [city4, city5], [city5, stop]] 
         if distance(graph, route) != "NO SUCH ROUTE" and len(route) >= minStops and len(route) <= maxStops: 
          routes.append(route) 
return routes 

Где numRoutes подается мой граф сети, где числа представляют расстояния:

[[0, 5, 0, 5, 7], [0, 0, 4, 0, 0], [0, 0, 0, 8, 2], [0, 0, 8, 0, 6], [0, 3, 0, 0, 0]] 

начальный город, конечный город и параметры для длины маршрутов.

дистанция проверяет, является ли маршрут жизнеспособным, а routeFromCity возвращает прикрепленные узлы каждому поданному в городе.

У меня есть ощущение, что существует гораздо более эффективный способ генерации всех маршрутов, особенно когда я перехожу к еще нескольким шагам, но я не могу заставить ничего работать.

Answer 1

Вы можете использовать рекурсивную функцию. Ваш maxStops может быть параметром, и каждый раз, когда вы вызываете, вы уменьшаете это на 1. Когда minStops равно 0, вы получаете результат. Когда maxStops равно 0, вы останавливаете рекурсию.

Вот пример кода:

def routesFromCity(x): 
    for i in range(2, 10): 
     yield x * i 

def findRoutes(start, stop, minStops, maxStops): 
    if start == stop: 
     if minStops <= 0: 
      yield [] 
    else: 
     if maxStops > 0: 
      for nextCity in routesFromCity(start): 
       for route in findRoutes(nextCity, stop, minStops - 1, maxStops - 1): 
        yield [(start, nextCity)] + route 

for route in findRoutes(1, 12, 2, 5): 
    print route 

Выход:

[(1, 2), (2, 4), (4, 12)] 
[(1, 2), (2, 6), (6, 12)] 
[(1, 2), (2, 12)] 
[(1, 3), (3, 6), (6, 12)] 
[(1, 3), (3, 12)] 
[(1, 4), (4, 12)] 
[(1, 6), (6, 12)]