How to Create a Matrix of outcome combinations based on conditions in Python?

Question

I am trying to figure out a simply way to get a combination of paths to the same start/end point from a given list in python.

For example suppose my list is

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

I am trying to use itertools.permutations() to generate the following paths, but not sure how to make it search any number of steps to get to A as the ending letter.

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

Answer 1

As I wrote in a comment, you have a directed graph (X/Y is an edge, X and Y are vertices) and you're trying to find all cycles, without any specific difficulty.

Here's an example of how you can create a graph (represented by an adjacency list) from your list and then rebuild the edges out of the detected cycles.

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

If the graph is small enough, a simple Depth First Seach will do the trick. You can take a look at this answer for instance:

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

This is far from the optimal solution, but you can replace graph_cycles by a better implementation (Tarjan's or Kosaraju's algorithm, see en.wikipedia.org/wiki/Strongly_connected_component.)

In both cases, you'll have to take special care of nodes pointing directly to themselves (X/X edges).