python - 找到元组对的所有可能组合，将每个组合合并成新序列

Question

我有一条按以下顺序在一条路线（地点序列）上行驶的巴士路线：-

Ayr - Newton - Troon - Paisley - Glasgow

IEroute = ['Ayr', 'Newton', 'Troon', 'Paisley', 'Glasgow']

我需要找到所有可能的方式来拆分旅程（总是从 Ayr 开始，到 Glasgow 结束，所以我有代码（python）可以找到每个对组合并将每个（元组）对附加到列表中。

pairs = [('Ayr', 'Newton'),('Ayr', 'Troon'),('Ayr', 'Paisley'),('Ayr', 'Glasgow'),('Newton', 'Troon'),('Newton', 'Paisley'),('Newton', 'Glasgow'),('Troon', 'Paisley'),('Troon', 'Glasgow'),('Paisley', 'Glasgow')]

我想要结束的是一个列表列表或元组列表（或最快的内存效率最高的序列），其中包含所有可能的对组合（从 Ayr 开始并在 Glasgow 结束）。

final_splits = [['Ayr', 'Glasgow'], ['Ayr', 'Newton', 'Glasgow'], ['Ayr', 'Newton', 'Troon', 'Glasgow'], ['Ayr', 'Newton', 'Troon', 'Paisley', 'Glasgow'], ['Ayr', 'Troon', 'Glasgow'], ['Ayr', 'Troon', 'Glasgow'], ['Ayr', 'Troon', 'Paisley', 'Glasgow']..........etc]

不是一件容易的事！任何人都可以帮忙吗？

Answer 1

假设每个组合都成对出现，则无需计算该中间步骤

>>> from itertools import combinations
>>> route = ['Ayr', 'Newton', 'Troon', 'Paisley', 'Glasgow']
>>> [(route[0],)+x+(route[-1],) for i in range(len(route)-1) for x in combinations(route[1:-1],i)]
[('Ayr', 'Glasgow'), ('Ayr', 'Newton', 'Glasgow'), ('Ayr', 'Troon', 'Glasgow'), ('Ayr', 'Paisley', 'Glasgow'), ('Ayr', 'Newton', 'Troon', 'Glasgow'), ('Ayr', 'Newton', 'Paisley', 'Glasgow'), ('Ayr', 'Troon', 'Paisley', 'Glasgow'), ('Ayr', 'Newton', 'Troon', 'Paisley', 'Glasgow')]