쌍으로 조합

Question

나는 감독 된 네트워크 문제를 해결하고 두 지점 사이의 모든 유효한 경로를 계산하려고합니다. 길이가 30 "여행"([출발지, 목적지] 쌍으로 표시)까지 경로를 볼 수있는 방법이 필요합니다.

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

이

지금까지 내 최고의 솔루션은 다음됩니다 과 같습니다 : 전체 경로는 다음이 쌍의 시리즈로 구성되어

: numRoutes 숫자가 거리를 대표하는 내 네트워크 그래프를 공급

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 

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

시작 도시, 종료 도시 및 경로 길이 매개 변수.

거리는 경로가 실행 가능하고 routesFromCity가 연결된 각 노드에 연결된 노드를 반환하는지 확인합니다.

나는 더 많은 단계로 나아감에 따라 모든 경로를 생성하는 훨씬 더 효율적인 방법이 있다는 느낌이 들지만, 다른 어떤 것도 작동시키지 못합니다.

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