通过Python生成器以有序顺序排列有向无环图中的所有唯一路径吗?

本文介绍了通过Python生成器以有序顺序排列有向无环图中的所有唯一路径吗?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有一个

我想通过一些生成器，以迭代方式，以迭代方式在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:设置([4])，2:设置([4])，3:设置([4])，4:set([5，6，7])，5:set([8])，6:set([8])，7:设置([8])}def dfs_paths(图形，开始，目标):堆栈= [(开始，[开始])]堆叠时:(顶点，路径)= stack.pop()对于graph [vertex]中的下一个-set(path):如果下一个==目标:屈服路径+ [下一个]别的:stack.append((下一个，路径+ [下一个]))def run_paths():以[1、2、3]开始:对于dfs_paths(graph，start，8)中的路径:打印路径

查找所有路径然后随机流式传输对我来说是行不通的，因为我不想存储将要生成的任何路径.

解决方案

请注意，您与自己矛盾:您希望输出严格无序"，但序列没有状态或存储空间.通过信息论根本不可能做到这一点.但是，如果您的目标只是简单地进行随机播放"，即偶然的观察者无法识别为预定顺序的不同顺序，那么您就有机会了.

首先，确定您的选择点和尺寸.例如，您上面的选择是[1、2、3] x [5、6、7].这使您可以生成3 * 3 = 9条路径.让我们在插图中添加第三个选择，即[T，F].这给出了3 * 3 * 2 = 18条路径.

现在，使用您喜欢的完美序列生成器"为您创建一个简单的函数.我假设在RNG进程中允许 something 调用以前的值或种子.为了简单起见，让我们使用平凡的线性序列 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，商22 divmod 3 =>mod 2，商00 divmod 2 =>模0

因此，您选择了三个选择数组中具有元素1、2、0的路径.生成的路径为(在粗体中选择了节点):

2 4 6 8 T

清楚吗?它可以解决您的问题吗?

I have a Directed Acyclic Graph (DAG), which consists of layers, with two subsequent layers being completely bipartite (much like a neural net), like the following:

I want to stream all paths in the DAG, in an iterative manner, via some generator, in a randomized order. Because, output must not be in order, textbook DFS approaches are out of question. Memory is an issue, so I don't want to store any paths that I have yielded before, except the DAG alone, which could be modified however is needed.

Example, the desired output for the above DAG is:

(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)

instead of the following produced by 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)

Thanks for your help.

Update:

I have the following code

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

Finding all paths and then randomly streaming them will not work for me, as I do not want to store any paths I will be generating.

解决方案

Please note that you're contradicting yourself: you want output to be "strictly unordered", but you have no state or memory for the sequence. This is simply not possible via information theory. However, if your goal is simply to have a "shuffle" -- a different sequence that a casual observer won't recognize as a predetermined sequence, then you have a chance.

First, determine your choice points and sizes. For instance, your choices above are [1, 2, 3] x [5, 6, 7]. This gives you 3*3 = 9 paths to generate. Let's add a third choice for illustration, a [T, F] on the end. This gives 3*3*2 = 18 paths.

Now, use your favorite "perfect sequence generator" to create a simple function for you. I'm assuming that something int he RNG process is allowed to recall the previous value or seed. For ridiculous simplicity, let's use a trivial linear sequence f(n) = f(n-1) + 5 (mod 18). This will give the sequence 0 5 10 15 2 7 12 17 ...

Now have your path generator call this function on each iteration. Simply convert the returned "random" number to digits in the given base sequence -- 3|3|2 in this case. Let's look at the value 7, taking the conversion from left to right, using the bases in order:

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

Thus, you choose the path with elements 1, 2, 0 of your three choice arrays. The resulting path is (chosen nodes in bold):

2 4 6 8 T

Is that clear? Does it solve your problem?