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

Question

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.

Answer 1

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?