How to translate pythonic double for loop to standard code?

Question

I have this chunk of pythonic code that I've been having trouble understanding:

paths = [[end]]
while paths and paths[0][0] != start:
    paths = [[parent] + path for path in paths for parent in childToParents[path[0]]]

where childToParents is:

defaultdict(<class 'set'>, {'cog': {'log', 'dog'},
                            'dog': {'dot'},
                            'dot': {'hot'},
                            'hit': None,
                            'hot': {'hit'},
                            'log': {'lot'},
                            'lot': {'hot'}})

end is "cog", start is "hit". The expected output of paths is:

[["hit","hot","lot","log","cog"],["hit","hot","dot","dog","cog"]]

I have tried multiple variations of a double for loop. One such attempt is:

    paths=[[end]]
    while paths and paths[0][0] != start:
        for i in xrange(len(paths)):
            for parent in childToParents[paths[i][0]]:
                paths[i] = [parent] + paths[i]

But this only gives me:

[["hit","hot","dot","dog","log","cog"]]

How can I translate the code to a standard double for loop?

Very generally speaking, there's no trivial way to turn an arbitrary while loop into a for loop. Most for loops have a definite end point, and many while loops never end. — Kevin
– Kevin, Commented Sep 25, 2018 at 13:32
I believe you can't. I mean, obviously you can replace any while with a for, just use for _ in count(): if not <condition>: break but this is just syntactic quibbling... In this specific case it seems like the code is doing something like visiting a graph or following a set of paths in a graph. You generally cannot predict how many iterations you'll do since it depends on the graph structure. — Giacomo Alzetta
– Giacomo Alzetta, Commented Sep 25, 2018 at 13:33
@Kevin I'm not concerned with the for loop on the outside. I'm concerned with the pythonic duoble for loop as stated in the post title — TheRealFakeNews
– TheRealFakeNews, Commented Sep 25, 2018 at 13:40

mfitzp · Accepted Answer · 2018-09-25 14:41:17Z

1

The nested for loop in the comprehension works left to right, so the rightmost loop is the inner loop, the left loop is the outer. For example —

a = [1,2,3]
b = [8,9,0]

[(a1, b1) for a1 in a for b1 in b]

Is equivalent to:

l = []
for a1 in a:
    for b1 in b:
      l.append((a1, b1))
l

Both will output the following if run

[(1, 8), (1, 9), (1, 0), (2, 8), (2, 9), (2, 0), (3, 8), (3, 9), (3, 0)]

For your example code —

paths = [[end]]
while paths and paths[0][0] != start:
    paths = [[parent] + path for path in paths for parent in childToParents[path[0]]]

Would be equivalent to:

paths = [[end]]
while paths and paths[0][0] != start:
    paths_, paths = paths, []
    for path in paths_:
        for parent in childToParents[path[0]]:
            paths.append([parent] + path)
paths

Note the paths_, paths = paths, [] needed to preserve the contents of paths to iterate over while still resetting it for the subsequent loop. Running the above with your inputs gives me:

[['hit', 'hot', 'dot', 'dog', 'cog'], ['hit', 'hot', 'lot', 'log', 'cog']]

edited Sep 25, 2018 at 14:41

answered Sep 25, 2018 at 13:53

mfitzp

15.6k7 gold badges55 silver badges72 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

martineau Over a year ago

paths.append([parent] + path]) -> SyntaxError: invalid syntax. Also, I think the OP wants to get rid of the while loop.

mfitzp Over a year ago

@martineau thanks, typo. I don't think he actually does, but it's not exactly clear.

martineau Over a year ago

Yeah, it's hard to say. +1 regardless.

TheRealFakeNews Over a year ago

@mfitzp Nope. Don't want to get rid of the while loop

TheRealFakeNews Over a year ago

@mfitzp If I try your solution, it seems that I just have paths as an empty list as my end result

|

Collectives™ on Stack Overflow

How to translate pythonic double for loop to standard code?

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related