Combinations into pairs
- by Will
I'm working on a directed network problem and trying to compute all valid paths between two points. I need a way to look at paths up to 30 "trips" (represented by an [origin, destination] pair) in length. The full route is then composed of a series of these pairs:
route = [[start, city2], [city2, city3], [city3, city4], [city4, city5], [city5, city6], [city6, city7], [city7, city8], [city8, stop]]
So far my best solution is as follows:
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
Where numRoutes is fed my network graph where numbers represent distances:
[[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]]
a start city, an end city and the parameters for the length of the routes.
distance checks if a route is viable and routesFromCity returns the attached nodes to each fed in city.
I have a feeling there's a far more efficient way to generate all of the routes especially as I move toward many more steps, but I can't seem to get anything else to work.
