Converting nested for loops which constructs and prints lists to a resursive function

Question

I'm trying to convert the following nested for loops which constructs and prints a list into a recursive function as it would greatly improve the runtime of it. However, I'm having difficulty with this. How could I go about converting it with so many layers of nested loops?

for v in range(-10, 11, 1):
     for w in range(-10, 11, 1):
            for x in range(-10, 11, 1):
                for y in range(-10, 11, 1):
                    for z in range(-10, 11, 1):
                        print([v, w, x, y, z])

Minor typo in the first line: for (v in range(-10, 11, 1)) should be for v in range(-10, 11, 1) I presume. Your point is clear nevertheless. — Thomas Fauskanger
– Thomas Fauskanger, Commented Feb 15, 2018 at 0:22
While recursion does have some advantages over iteration, performance is generally not one of them. Especially not in Python, which by default, doesn't optimize tail recursion. Is there any other reason you need this to be in the form of a recursive function? — mypetlion
– mypetlion, Commented Feb 15, 2018 at 0:22
@mypetlion Honestly, I'm just trying to see if I'd get any performance advantages as well as it being a personal challenge. — Paradox
– Paradox, Commented Feb 15, 2018 at 0:24

G_M · Accepted Answer · 2018-02-15 00:45:54Z

4

As @mypetlion mentioned above, recursion in Python might not give you the performance boost you are looking for.

What about using itertools.product? I haven't benchmarked it compared to your original but it does seem to be implemented in C.

from itertools import product

for p in product(range(-10, 11), repeat=5):
    print(p)

edited Feb 15, 2018 at 0:45

answered Feb 15, 2018 at 0:37

G_M

3,3821 gold badge11 silver badges24 bronze badges

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

1 Comment

kszl Over a year ago

I was about to mention the same solution. According to the documentation "This function (...) does not build up intermediate results in memory", so it is a perf win. Moreover, if there was something else to optimize, I'm pretty sure they'd do that.

Sebastien D · Accepted Answer · 2018-02-15 00:58:14Z

1

If I understood well, this could be a combination with replacement function done with itertools:

import itertools
import numpy as np

comb =  list(itertools.combinations_with_replacement(range(-10,11,1), 5))

for x in comb:
    print  np.asarray(x)

edited Feb 15, 2018 at 0:58

answered Feb 15, 2018 at 0:46

Sebastien D

4,5024 gold badges23 silver badges50 bronze badges

3 Comments

G_M Over a year ago

Still doesn't match the output of the original. Your last two lines: [ 9 10 10 10 10]; [10 10 10 10 10] VS Original last two lines: [10, 10, 10, 10, 9]; [10, 10, 10, 10, 10]. If you just run the original code you will see that the pattern does not match the output of combinations_with_replacement.

Sebastien D Over a year ago

Alright I see, the output order matters this is it?

G_M Over a year ago

This link shows the last few lines of your output VS the original codes output (the outputs are totally different): bpaste.net/show/bbb6497d707d

Ajax1234 · Accepted Answer · 2018-02-15 00:54:01Z

0

You can create default list in the function signature to store the elements you have currently accumulated, and once the length of the list equals the desired amount, yield the current list:

def combinations(count, args, current = []): 
    if len(current) == count:
       yield current
    else:
       for i in range(*args):
         yield from combinations(count, args, current + [i])

print(list(combinations(5, [-10, 11])))

edited Feb 15, 2018 at 0:54

answered Feb 15, 2018 at 0:23

Ajax1234

71.7k9 gold badges67 silver badges110 bronze badges

2 Comments

mypetlion Over a year ago

You're using both iteration and recursion here, which is not what the question asked for. Your print statement also doesn't produce the desired output.

Ajax1234 Over a year ago

@mypetlion The OP does not specifically state that all loops were to be eliminated from the recursion. However, I did fix the print statement so that the generator expression will be forced to retrieve all combinations in memory.

Collectives™ on Stack Overflow

Converting nested for loops which constructs and prints lists to a resursive function

3 Answers 3

1 Comment

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related