从一组边高效地创建和存储所有 "valid" 个所有大小的边组合

Question

我认为这是一个相当困难的问题。因此，提前感谢您的帮助。

我有一个正在遍历的图表，一次创建一条不同的路径。我有一组我 "must" 使用的边缘，每个边缘都存储为（到，从）的元组。我避免重复节点，所以我们只去每个 "to" 一次，每个 "from" 一次。我也不想在组合中创建循环。

我想创建边的所有组合（顺序很重要）。具体来说，我想要所有有效大小的元组的所有组合。

为清楚起见，举几个例子：

Valid combinations of edges:

((5,7))
((3,9),(9,11),(21,18))
((1,2),(2,3),(3,4),(4,5))

Invalid combinations:
((9,8),(9,6))
((2,5),(11,3),(8,5))
((1,2),(2,3),(3,4),(4,1))

所以，我们可以看到一件事，就是要进行所有组合，我们将进行尺寸 1 的组合，然后是尺寸 2，然后是尺寸 3，... 4....n

别担心，没那么疯狂。我创建组合的边数通常不多。但它是可变的，谁知道呢，也许我最终可以创建一些大小为 n 的组合。

所以，我在考虑使用 itertools 来生成组合。我可以将 itertools 组合放在一个循环中，并增加每次传递的组合大小。

但后来我意识到，很可能大多数组合最终都会无效，如果我使用 itertools，我认为在生成整个组合之前我无法检查它们的有效性。这似乎非常低效。

所以，我的想法是使用邻接表，其中我想要强制的任何边（到，从）都存储在索引 [to][from] 中。这允许我迭代邻接列表，以避免得到重复的 "to"s 或重复的 "froms".

但是，我仍然无法概念化如何实际编写一个函数，通过遍历邻接列表生成我想要的所有组合。

有什么想法吗？

注意：目前，我不介意是否有人选择忽略避免闭环的挑战，即：1,2,3,4,1

Answer 1

下面是一个递归生成器函数。它将边缘列表预处理为邻接字典。它将生成所有长度为 l:

的路径

from collections import defaultdict

# preprocess for better performance
edges = [(1,2),(2,1),(2,3),(3,4),(4,5),(5,7), (3,9),(9,11),(11,18)]
graph = defaultdict(set)
for f, t in edges:
    graph[f].add(t)

def paths(graph, l, fr=None, avoid=None):
    avoid = avoid or set()  # avoid previous nodes
    if l == 0:  # base case: empty path
        yield ()
    from_nodes = [fr] if fr else graph.keys()
    for f in from_nodes:
        new_avoid = avoid | set([f])  # set union
        for t in graph[f]:  # for every adjacent node t...
            if t not in avoid:  # unless it has been seen
                # take all paths starting at t with length l-1
                for path in paths(graph, l-1, fr=t, avoid=new_avoid):
                    # and prepend the current edge
                    yield ((f, t),) + path 

>>> list(paths(graph, 2))
[((1, 2), (2, 3)),
 ((2, 3), (3, 9)),  # no cycle: ((1, 2), (2, 1))
 ((2, 3), (3, 4)),
 ((3, 9), (9, 11)),
 ((3, 4), (4, 5)),
 ((4, 5), (5, 7)),
 ((9, 11), (11, 18))]

>>> list(paths(graph, 3))
[((1, 2), (2, 3), (3, 9)),
 ((1, 2), (2, 3), (3, 4)),
 ((2, 3), (3, 9), (9, 11)),
 ((2, 3), (3, 4), (4, 5)),
 ((3, 9), (9, 11), (11, 18)),
 ((3, 4), (4, 5), (5, 7))]

从一组边高效地创建和存储所有 "valid" 个所有大小的边组合

Efficiently creating and storing all "valid" edge combinations of all sizes from a set of edges

python

algorithm

graph

traveling-salesman

combinatorics