Better equivalent of this crazy nested python for loop

Question

for a in map:
    for b in map[a]:
        for c in map[b]:
            for d in map[c]:
                for e in map[d]:
                    print a+b+c+d+e

The above code is used to create all paths of certain length in a graph. map[a] represents the points you can reach from point a.

How can I change it to simulate having an arbitrary number of loops?

This is like a cartesian product (itertools.product) where at each iteration your choice for the next element is limited to those in map[current_point].

Well, you have tagged it with recursion.. did you try that? – wim Jan 18 '12 at 07:11 — wim, Jan 18 '12 at 07:11

Baffe Boyois · Accepted Answer · 2012-01-18T16:51:33.013

6

map = {
    'a': ['b', 'c'],
    'b': ['c', 'd'],
    'c': ['d', 'a'],
    'd': []
}

def print_paths(map, start, length, prefix = ''):
    if length == 0:
        print prefix
    else:
        for a in map[start]:
            print_paths(map, a, length - 1, prefix + start)

for a in map.keys():
    print_paths(map, a, 5)

edited Jan 18 '12 at 16:51

answered Jan 18 '12 at 07:09

Baffe Boyois

2,120
15
15

1

I'm sorry I forgot to mention map[a][b] is an integer that represents the distance between a to b. So your solution stops working as soon as it hits the integer. Can you tell me how to change it to an exact equivalent of the nested loop? So the function doesn't go beyond map[a]. (map[X] is enough for any given point X since your choice about where you can go next from a certain point doesn't depend on how you got there) – Babak Jan 18 '12 at 07:42
If map[a][b] is an integer, your original code can't work. Could you update the question with a working example of `map`? I'll add the kind of `map` I assumed to this answer. – Baffe Boyois Jan 18 '12 at 16:42
...and edit the answer to actually work, since neither I nor the 5 upvoters noticed that it didn't... – Baffe Boyois Jan 18 '12 at 16:52

dani herrera · Answer 2 · 2012-01-18T12:24:25.470

This is a classical recursive problem. Your function should returns concatenation of node value with all results of your function result for each child node. As you can see in sentence, function behavior is explained in a recursive way:

myGraph = { 1:[2,3], 2:[3,4] }

def recorre( node_list, p = '' ):    
    for node in node_list:
        if node in myGraph and myGraph[node]: 
            recorre(myGraph[node], p+unicode( node ))
        else:
            print p+unicode( node )

recorre( myGraph )

Result:

>>> recorre( myGraph )
123
124
13
23
24

This code is a start point. You can store all paths in a list, use yield generator, etc. Don't forget to prevent circles.

Also, take a look to igraph solution. Sure this library can helps to you, see this example: Finds all shortest paths (geodesics) from a vertex to all other vertices.

Regards.

score 1 · Answer 3 · answered Jan 18 '12 at 10:50

Just like other suggested, with recursion:

    distances = []        

    def compute_distance(map, depth, sum):
         if depth == 0 or len(map) == 0:
            distances.append[sum]
         else:
            for a in map:
               compute_distance(map[a], depth - 1, sum + a)

   compute_distance(map, x, 0)

Better equivalent of this crazy nested python for loop

3 Answers3

Linked