对组合的所有可能路径

Question

我不知道这个连接组件的正确名称，但我正在寻找的是用 pairs/edges 列表的所有可能组合形成路径。给定一个列表：

("A", "B")
("A", "C")
("A", "D")
("C", "D")
("D", "B")
("D", "E")
("E", "F")

我希望我的输出与此类似：

("A", "B")
("B", "A")
("A", "C")
("C", "A")
("A", "D")
("D", "A")
("C", "D")
("D", "C")
...
("A", "B", "D")
("A", "C", "D")
("A", "D", "B")
("A", "D", "C")
("A", "D", "E")
("B", "A", "C")
("B", "A", "D")
("B", "D", "A")
("B", "D", "C")
("B", "D", "E")
...
("A", "B", "D", "E")
("A", "C", "D", "E")
...
("A", "B", "D", "E", "F")
...
("F", "E", "D", "B", "A")

我只需要四到五个组合（取决于输出的大小）。

我在 more_itertools.distinct_permutations and networkx.algorithms.clique.enumerate_all_cliques

中找到了与我要查找的内容隐约相关的内容

Answer 1

您的任务可以通过常规 Depth First Search approach of Graph traversal using Recursive 功能轻松解决。

我下面的代码完全实现了这种方法。只需使用给定的边列表调用 all_paths() 函数，它将 return 所有可能的路径达到所需的最大长度。

这个函数有一些额外的参数allow_same_vertices = False, allow_same_edges = False, max_length = 5。第一个参数表示是否允许在单个路径中重复相同的顶点两次。第二个表示是否允许重复相同的边两次（有时可能允许重复相同的顶点但不重复相同的边）。第三个参数表示允许的最大路径长度。

这个深度优先搜索是如何工作的：递归函数从某个顶点开始，然后它尝试访问这个顶点的所有邻居（通过跟踪当前顶点的所有边），如果邻居存在于一组被访问的顶点中那么这个neighour 被跳过，否则将邻居添加到访问的顶点并添加到路径，并以该邻居作为参数再次调用递归函数。递归调用完成后，从路径和访问的顶点中删除邻居。

这种图的递归深度优先搜索遍历保证遍历所有可能的路径，是众所周知的算法。

Try it online!

def all_paths(edges, *, allow_same_vertices = False, allow_same_edges = False, max_length = 5):
    neighbours = {None: []}
    for a, b in edges:
        for i in range(2):
            if a not in neighbours[None]:
                neighbours[None].append(a)
            if a not in neighbours:
                neighbours[a] = []
            if b not in neighbours[a]:
                neighbours[a].append(b)
            a, b = b, a
    visited_edges = {}
    visited_vertices = {}
    paths = set()
    path = []
    def rec(vertex):
        if len(path) >= 2:
            paths.add(tuple(path))
        if len(path) >= max_length:
            return
        for neighbour in neighbours.get(vertex, []):
            if not allow_same_vertices and visited_vertices.get(neighbour, 0) > 0:
                continue
            if not allow_same_edges and visited_edges.get((vertex, neighbour), 0) > 0:
                continue
            visited_vertices[neighbour] = visited_vertices.get(neighbour, 0) + 1
            visited_edges[(vertex, neighbour)] = visited_edges.get((vertex, neighbour), 0) + 1
            path.append(neighbour)
            rec(neighbour)
            path.pop()
            visited_vertices[neighbour] -= 1
            visited_edges[(vertex, neighbour)] -= 1
    rec(None)
    return sorted(paths, key = lambda e: (len(e), e))

def main():
    for path in all_paths([
        ("A", "B"),
        ("A", "C"),
        ("A", "D"),
        ("C", "D"),
        ("D", "B"),
        ("D", "E"),
        ("E", "F"),
    ], max_length = 4):
        print(path)

main()

输入：

("A", "B"),
("A", "C"),
("A", "D"),
("C", "D"),
("D", "B"),
("D", "E"),
("E", "F"),

输出：

('A', 'B')
('A', 'C')
('A', 'D')
('B', 'A')
('B', 'D')
('C', 'A')
('C', 'D')
('D', 'A')
('D', 'B')
('D', 'C')
('D', 'E')
('E', 'D')
('E', 'F')
('F', 'E')
('A', 'B', 'D')
('A', 'C', 'D')
('A', 'D', 'B')
('A', 'D', 'C')
('A', 'D', 'E')
('B', 'A', 'C')
('B', 'A', 'D')
('B', 'D', 'A')
('B', 'D', 'C')
('B', 'D', 'E')
('C', 'A', 'B')
('C', 'A', 'D')
('C', 'D', 'A')
('C', 'D', 'B')
('C', 'D', 'E')
('D', 'A', 'B')
('D', 'A', 'C')
('D', 'B', 'A')
('D', 'C', 'A')
('D', 'E', 'F')
('E', 'D', 'A')
('E', 'D', 'B')
('E', 'D', 'C')
('F', 'E', 'D')
('A', 'B', 'D', 'C')
('A', 'B', 'D', 'E')
('A', 'C', 'D', 'B')
('A', 'C', 'D', 'E')
('A', 'D', 'E', 'F')
('B', 'A', 'C', 'D')
('B', 'A', 'D', 'C')
('B', 'A', 'D', 'E')
('B', 'D', 'A', 'C')
('B', 'D', 'C', 'A')
('B', 'D', 'E', 'F')
('C', 'A', 'B', 'D')
('C', 'A', 'D', 'B')
('C', 'A', 'D', 'E')
('C', 'D', 'A', 'B')
('C', 'D', 'B', 'A')
('C', 'D', 'E', 'F')
('D', 'B', 'A', 'C')
('D', 'C', 'A', 'B')
('E', 'D', 'A', 'B')
('E', 'D', 'A', 'C')
('E', 'D', 'B', 'A')
('E', 'D', 'C', 'A')
('F', 'E', 'D', 'A')
('F', 'E', 'D', 'B')
('F', 'E', 'D', 'C')

对组合的所有可能路径

All possible paths from pair combinations

python

networkx

more-itertools