python - 有向无环图中的所有唯一路径，以随机顺序，通过 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

请注意，您是在自相矛盾:您希望输出“严格无序”，但您没有序列的状态或内存。这通过信息论根本不可能。但是，如果您的目标只是进行“洗牌”——随意的观察者不会将其识别为预先确定的顺序的不同顺序，那么您就有机会了。

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

现在，使用您最喜欢的“完美序列生成器”为您创建一个简单的函数。我假设允许 RNG 过程中的某物 调用以前的值或种子。为简单起见，让我们使用一个简单的线性序列 f(n) = f(n-1) + 5 (mod 18)。这将给出序列 0 5 10 15 2 7 12 17 ...

现在让您的路径生成器在每次迭代时调用此函数。只需将返回的“随机”数字转换为给定基本序列中的数字——在本例中为 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

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