Поиск комбинаций элементов в списке на основе маршрутизации

Question

Я не уверен, как устно express того, чего я хочу достичь, и сформулировать правильный вопрос для этого, поэтому вот пример:

Если у меня есть исчерпывающий список с такими элементами:

list = ['A to B', 'B to C', 'C to D', 'D to E', 'A to C', 'A to D', 'A to E',
 'B to A', 'B to C', 'B to D', 'B to E', 'C to A', 'E to B', 'E to C', 'E to A']

Я хотел бы найти все уникальные комбинации ровно 3 элементов, выражающих маршрутизацию, и впоследствии сохранить эти комбинации в отдельных списках, например:

['A to B', 'B to C', 'C to A'],

['B to C', 'C to A', 'A to B'],

etc.

Итак, в В первом примере вывода A возвращается обратно к A, а во втором выводе B возвращается обратно к B. Я хотел бы, чтобы что-либо возвращалось к себе таким образом.

Я новичок в Python и пытаюсь придумать, как это сделать, но застрял.

Как мне этого добиться?

Answer 1

Возможно, использование перестановок из itertools, возможно, не лучший выбор, но он дает результат, который вы хотели

#importing permutations from itertools
from itertools import permutations as c
lst= ['A to B', 'B to C', 'C to D', 'D to E', 'A to C', 'A to D', 'A to E',
 'B to A', 'B to C', 'B to D', 'B to E', 'C to A', 'E to B', 'E to C', 'E to A']
#permutation of the list with r as 3
lst_com = c(lst,3)
# this list is to reduce redundancy
d=[]
for i in lst_com:
    t=list(i)
    # if statement to check the express routing and not include redundant values
    if t[0][0] == t[2][-1] and t[0][-1] == t[1][0] and t[1][-1]==t[2][0] and t not in d:
        d.append(t)
        print(t)

Вывод:

['A to B', 'B to C', 'C to A']
['A to B', 'B to E', 'E to A']
['B to C', 'C to A', 'A to B']
['C to D', 'D to E', 'E to C']
['D to E', 'E to B', 'B to D']
['D to E', 'E to C', 'C to D']
['D to E', 'E to A', 'A to D']
['A to D', 'D to E', 'E to A']
['A to E', 'E to B', 'B to A']
['A to E', 'E to C', 'C to A']
['B to A', 'A to E', 'E to B']
['B to D', 'D to E', 'E to B']
['B to E', 'E to A', 'A to B']
['C to A', 'A to B', 'B to C']
['C to A', 'A to E', 'E to C']
['E to B', 'B to A', 'A to E']
['E to B', 'B to D', 'D to E']
['E to C', 'C to D', 'D to E']
['E to C', 'C to A', 'A to E']
['E to A', 'A to B', 'B to E']
['E to A', 'A to D', 'D to E']

Answer 2

Я бы посоветовал поместить все шаги в словарь key -> list of keys, к которому они приводят.

Вы можете запросить это, чтобы получить все триплеты:

data = ['A to B', 'B to C', 'C to D', 'D to E', 'A to C', 'A to D', 'A to E',
 'B to A', 'B to C', 'B to D', 'B to E', 'C to A', 'E to B', 'E to C', 'E to A']

from collections import defaultdict
routes = defaultdict(list)

for d in data:
    frm, to = d.split(" to ")
    routes[frm].append(to)

print (routes)

plets = set()

for frm, to in routes.items():
    for target in to:
        for target2 in routes[target]:
            if frm in routes[target2]: 
                plets.add( (frm, target, target2, frm) )

for t in sorted(plets):
    print(*t, sep= " -> ") 

Вывод:

defaultdict(<class 'list'>, {'A': ['B', 'C', 'D', 'E'], 
                             'B': ['C', 'A', 'C', 'D', 'E'], 
                             'C': ['D', 'A'], 
                             'D': ['E'], 
                             'E': ['B', 'C', 'A']})

A -> B -> C -> A
A -> B -> E -> A
A -> D -> E -> A
A -> E -> B -> A
A -> E -> C -> A
B -> A -> E -> B
B -> C -> A -> B
B -> D -> E -> B
B -> E -> A -> B
C -> A -> B -> C
C -> A -> E -> C
C -> D -> E -> C
D -> E -> A -> D
D -> E -> B -> D
D -> E -> C -> D
E -> A -> B -> E
E -> A -> D -> E
E -> B -> A -> E
E -> B -> D -> E
E -> C -> A -> E
E -> C -> D -> E

Использование набора для хранения ваших возможных маршрутов позволяет избежать повторения одних и тех же маршрутов несколько раз .

---

Редактировать для вывода:

def formIt(a,b,c,d):
    return f"{a} to {b}",f"{b} to {c}",f"{c} to {d}"

for frm, to in routes.items():
    for target in to:
        for target2 in routes[target]:
            if frm in routes[target2]: 
                plets.add( formIt(frm, target, target2, frm) )

for t in sorted(plets):
    print(*t, sep = ", ") 

, чтобы получить

A to B, B to C, C to A 
A to B, B to E, E to A 
A to D, D to E, E to A 
 ... snipp...
E to C, C to A, A to E 
E to C, C to D, D to E