通过 Python 生成器以随机顺序在有向无环图中的所有唯一路径？

Question

我有一个 Directed Acyclic Graph (DAG)，它由层组成，两个后续层完全是二分的（很像神经网络），如下所示：

我想流 DAG 中的所有路径，以迭代方式，通过一些生成器，以随机顺序排列。因为，输出不能按顺序，教科书 DFS 方法是不可能的。内存是个问题，所以我不想存储我之前生成的任何路径，除了 DAG 之外，它可以修改但是需要。

例如，上述 DAG 的期望输出是：

(1, 4, 6, 8)
(3, 4, 5, 8)
(2, 4, 7, 8)
(3, 4, 6, 8)
(1, 4, 5, 8)
(3, 4, 7, 8)
(1, 4, 7, 8)
(2, 4, 6, 8)
(2, 4, 5, 8)

而不是 DFS 生成的以下内容：

(1, 4, 5, 8)
(1, 4, 6, 8)
(1, 4, 7, 8)
(2, 4, 5, 8)
(2, 4, 6, 8)
(2, 4, 7, 8)
(3, 4, 5, 8)
(3, 4, 6, 8)
(3, 4, 7, 8)

感谢您的帮助。

更新：

我有以下代码

graph = {
    1: set([4]),
    2: set([4]),
    3: set([4]),
    4: set([5, 6, 7]),
    5: set([8]),
    6: set([8]),
    7: set([8])
}

def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    while stack:
        (vertex, path) = stack.pop()
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                stack.append((next, path + [next]))

def run_paths():
    for start in [1, 2, 3]:
        for path in dfs_paths(graph, start, 8):
            print path

找到所有路径然后随机流式传输它们对我不起作用，因为我不想存储我将生成的任何路径。

Answer 1

请注意，您是在自相矛盾：您希望输出为 "strictly unordered"，但您没有序列的状态或记忆。这通过信息论根本不可能。但是，如果您的目标只是获得一个 "shuffle" -- 一个不经意的观察者不会将其识别为预定序列的不同序列，那么您就有机会了。

首先，确定您选择的点数和尺寸。例如，您上面的选择是 [1, 2, 3] x [5, 6, 7]。这为您提供了 3*3 = 9 个生成路径。让我们添加第三个选项来说明，最后是 [T, F]。这给出了 3*3*2 = 18 条路径。

现在，使用您最喜欢的 "perfect sequence generator" 为您创建一个简单的函数。我假设 something 允许 RNG 进程调用以前的值或种子。为简单起见，让我们使用一个平凡的线性序列 f(n) = f(n-1) + 5 (mod 18)。这将给出序列 0 5 10 15 2 7 12 17 ...

现在让您的路径生成器在每次迭代时调用此函数。只需将返回的 "random" 数字转换为给定基本序列中的数字——在本例中为 3|3|2。让我们看看值 7，从左到右进行转换，按顺序使用基数：

7 divmod 3 => mod 1, quotient 2
2 divmod 3 => mod 2, quotient 0
0 divmod 2 => mod 0

因此，您选择了包含三个选择数组中的元素 1、2、0 的路径。结果路径是（粗体中选择的节点）：

2 4 6 8 T

说清楚了吗？它能解决您的问题吗？

通过 Python 生成器以随机顺序在有向无环图中的所有唯一路径？

All unique paths in a directed acyclic graph, in randomized order, via Python generator?

python

algorithm

generator

graph-algorithm

data-structures