Как создать матрицу комбинаций результатов на основе условий в Python?

Question

Я пытаюсь найти простой способ получить комбинацию путей к одной и той же начальной / конечной точке из заданного списка в python.

Например, предположим, что мой список

list1 = ['A/B','B/A','B/C','C/D','C/A','D/E,'E/C']

Я пытаюсь использовать itertools.permutations() для генерации следующих путей, но не уверен, как заставить его искать любое количество шагов, чтобы добраться доA как конечная буква.

[('A/B','B/C','C/A'),('A/B','B/C','C/D','C/A'),('A/B','B/A')]

Answer 1

Как я писал в комментарии, у вас есть ориентированный граф (X / Y - ребро, X и Y - вершины), и вы пытаетесь найти все циклы без каких-либо особых затруднений.

Вот пример того, как вы можете создать график (представленный списком смежности) из вашего списка, а затем перестроить ребра из обнаруженных циклов.

def get_cycles(edges):
    # create the graph from the edges
    graph = {}
    for e in edges:
        v1, v2 = e.split('/')
        graph.setdefault(v1, []).append(v2)

    for cycle in graph_cycles(graph):
        # rebuld the edges from the cycle
        if len(cycle) == 1:
            yield (cycle[0]+"/"+cycle[0], )
        else:
            # zip a,b,...,y,z with b,c,...,z,a to get the edges a/b, b/c, ..., y/z, z/a
            yield tuple([a+"/"+b for a,b in zip(cycle[-1:]+cycle[:-1], cycle)])

print (list(get_cycles(['A/A', 'A/B','B/A','B/C','C/D','C/A','D/E','E/C'])))
# output: [('A/B', 'B/C', 'C/A'), ('A/B', 'B/A'), ('A/A',), ('B/C', 'C/A', 'A/B'), ('B/A', 'A/B'), ('C/A', 'A/B', 'B/C'), ('C/D', 'D/E', 'E/C'), ('D/E', 'E/C', 'C/D'), ('E/C', 'C/D', 'D/E')]

Если график достаточно мал, простая глубинаПервый Seach сделает свое дело.Вы можете взглянуть на этот ответ , например:

def graph_cycles(graph):
    return (cycle for node in graph for cycle in dfs(graph, node, node)) # dfs defined in https://stackoverflow.com/a/40834276

Это далеко от оптимального решения, но вы можете заменить graph_cycles на лучшую реализацию (алгоритм Тарьяна или Косараджу, см. en.wikipedia.org/wiki/Strongly_connected_component.)

В обоих случаях вам нужно будет позаботиться об узлах, указывающих непосредственно на себя (ребра X / X).