如何在 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')]

如果图形足够小，一个简单的深度优先搜索就可以了。例如，你可以看看这个答案：

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通过更好的实现(Tarjan或Kosaraju的算法，见 en.wikipedia.org/wiki/Strongly_connected_component。

在这两种情况下，您都必须特别注意直接指向自身的节点(X/X 边(。