Suche alle möglichen Kombinationen von Tupels Paare verschmelzenden jeweils in neue Sequenzen

Question

I einen Busweg haben, der auf einer Strecke (Reihenfolge der Orte) in dieser Reihenfolge bewegt: -

Ayr - Newton - Troon - Paisley - Glasgow 

dh route = ['Ayr', 'Newton', 'Troon', 'Paisley', 'Glasgow']

I benötigten jede mögliche Art und Weise finden Sie die Reise nach oben aufspalten (beginnend immer in Ayr in Glasgow endet, so habe ich Code (python), die jede Paarkombination und fügt jedes (Tupel) Paar in eine Liste findet.

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

Was ich möchte, ist eine Liste von Listen oder Liste von Tupeln (oder die schnellste speichereffiziente Sequenz), die jede mögliche Kombination von Paaren hat (die in Ayr beginnt und in Glasgow endet).

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] 

Kein einfacher! Kann jemand helfen?

Answer 1

Unter der Annahme, jede Kombination paarweise auftreten würde, gibt es keine Notwendigkeit zu berechnen, dass Zwischenschritt

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