You understand that this will produce a very large number of routes and that it could take a long time to compute if your list gets much larger.
What you can do is progressively build a list of routes that you extend with new routes formed by connecting pairs to the beginning or end of the routes you have so far:
List = [[0.5,1],[0.75,1],[0.5,1.5],[0.75,1.5],[1,1.5],[0.5,2],[0.75,2],[1,2],[1.5,2],[0.75,3],[1,3],[1.5,3],[2,3],[1,4],[1.5,4],[2,4],[3,4],[1.5,6],[2,6],[3,6],[4,6],[3,8],[2,8],[4,8],[6,8],[3,10],[4,10],[6,10],[8,10],[4,12],[6,12],[8,12],[10,12],[6,14],[8,14],[10,14],[12,14],[6,16],[8,16],[10,16],[12,16],[14,16],[10,18],[12,18],[14,18],[16,18],[10,20],[12,20],[14,20],[16,20],[18,20],[14,24],[16,24],[18,24],[20,24],[22,24],[18,26],[20,26],[22,26],[24,26],[18,28],[20,28],[24,28],[26,28],[20,30],[24,30],[26,30],[28,30],[24,32],[26,32],[28,32],[30,32],[24,34],[26,34],[30,34],[32,34],[24,36],[26,36],[30,36],[32,36],[34,36],[24,42],[26,42],[30,42],[32,42],[34,42],[36,42],[36,48],[40,48],[42,48],[44,48],[46,48]]
routes = []
for pair in List:
inValue,outValue = pair
newRoutes = [[pair]]
for path in routes:
if path[0][0] == outValue:
newRoutes.append([pair] + path)
if path[-1][-1] == inValue:
newRoutes.append(path + [pair])
routes.extend(newRoutes)
output:
print("number of routes:",len(routes))
for route in routes[:10]:
print(route)
print("...")
for route in routes[-10:]:
print(route)
number of routes: 5646987
[[0.5, 1]]
[[0.75, 1]]
[[0.5, 1.5]]
[[0.75, 1.5]]
[[1, 1.5]]
[[0.5, 1], [1, 1.5]]
[[0.75, 1], [1, 1.5]]
[[0.5, 2]]
[[0.75, 2]]
[[1, 2]]
...
[[0.75, 1], [1, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[1.5, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[0.5, 1.5], [1.5, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[0.75, 1.5], [1.5, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[1, 1.5], [1.5, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[0.5, 1], [1, 1.5], [1.5, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[0.75, 1], [1, 1.5], [1.5, 2], [2, 3], [3, 4], [4, 6], [6, 8], [8, 10], [10, 12], [12, 14], [14, 16], [16, 18], [18, 20], [20, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[22, 24], [24, 26], [26, 28], [28, 30], [30, 32], [32, 34], [34, 36], [36, 42], [42, 48]]
[[44, 48]]
[[46, 48]]
Note that this can be optimized by indexing the existing routes on their first/last value. Optimizing like that will make it twice as fast but it won't reduce the number of routes in the output:
routesFirst = dict()
routesLast = dict()
routes = []
for pair in List:
inValue,outValue = pair
newRoutes = [[pair]]
for path in routesFirst.get(outValue,[]):
newRoutes.append([pair]+path)
for path in routesLast.get(inValue,[]):
newRoutes.append(path+[pair])
routes.extend(newRoutes)
routesFirst.setdefault(inValue,[]).extend(newRoutes)
routesLast.setdefault(outValue,[]).extend(newRoutes)
[EDIT] recursive approach (added for good measure):
If you are not going to go through all the paths, you can create a recursive generator function that will return them one by one. You can use it in a for loop (for example) that you intend to break when a certain condition is met.
Here is a very simple example (not optimized with meoization or anything):
def findRoutes(pairs,previous=None):
for pair in pairs:
inValue,outValue = pair
if inValue != previous and previous is not None:
continue
yield [pair]
for subRoute in findRoutes(pairs,outValue):
yield [pair] + subRoute
output:
for route in findRoutes(List):
if len(route) == 5:
print("first 5 step route:",route)
break
# first 5 step route: [[0.5, 1], [1, 1.5], [1.5, 2], [2, 3], [3, 4]]
[EDIT2] Finding a path from one number to another
To help with understanding the generator, I implemented a simple variant that will only return paths that connect two specific numbers. It still needs to use recursion but instead of going through all possible connections, it only looks at the ones that start from the given origin and stops when the destination is reached. For multi-step paths, the same function is called for each possible outValue that connect from the origin.
def findPath(pairs,origin,destination):
for pair in pairs:
inValue,outValue = pair
if inValue != origin:
continue
if outValue == destination :
yield [pair]
continue
for subPath in findPath(pairs,outValue,destination):
yield [pair] + subPath
output:
List = [[0.5,1],[0.75,1],[0.5,1.5],[0.75,1.5],[1,1.5],[0.5,2],[0.75,2],[1,2],[1.5,2],[0.75,3],[1,3],[1.5,3],[2,3],[1,4],[1.5,4],[2,4],[3,4],[1.5,6],[2,6],[3,6],[4,6],[3,8],[2,8],[4,8],[6,8],[3,10],[4,10],[6,10],[8,10],[4,12],[6,12],[8,12],[10,12],[6,14],[8,14],[10,14],[12,14],[6,16],[8,16],[10,16],[12,16],[14,16],[10,18],[12,18],[14,18],[16,18],[10,20],[12,20],[14,20],[16,20],[18,20],[14,24],[16,24],[18,24],[20,24],[22,24],[18,26],[20,26],[22,26],[24,26],[18,28],[20,28],[24,28],[26,28],[20,30],[24,30],[26,30],[28,30],[24,32],[26,32],[28,32],[30,32],[24,34],[26,34],[30,34],[32,34],[24,36],[26,36],[30,36],[32,36],[34,36],[24,42],[26,42],[30,42],[32,42],[34,42],[36,42],[36,48],[40,48],[42,48],[44,48],[46,48]]
for path in findPath(List,1,3):
print(path)
[[1, 1.5], [1.5, 2], [2, 3]]
[[1, 1.5], [1.5, 3]]
[[1, 2], [2, 3]]
[[1, 3]]
