Python Recursive Generator

Question

I'm trying to make a recursive generator, but I'm clearly missing something. Basically I have a list of positive and negative values for specific dimensions of a histogram, and want to get every combination of positive and negative. Ex:

input = [[-1,2],[-3,4],[-5,6]]

And the result I need is (although I want this as a generator instead of a list, but you get the idea):

output = [[-1, -3, -5],[-1, -3, 6],[-1, 4, -5],[-1, 4, 6],[2, -3, -5],[2, -3, 6],[2, 4, -5],[2, 4, 6]]

I have managed to get it done, but only by appending items to a global list inside of my recursion, but I really was hoping I could just do this with a generator and iterate over my function since that would make it so much cleaner IMO.

Here's what I have now:

def combs(idx,array,current=[]):
    for item in array[idx]:
        current_copy = current[:]
        current_copy.append(item)
        if idx + 1 < len(array):
            combs(idx+1,array,current_copy)
        else:
            print current_copy
            # yield current_copy

This will print out exactly what I want, but when I try to change the print to a yield and loop over the function it doesn't work. (e.g.)

for item in combs(0,input,[]):
    print item

Please, avoid calling your variables with function names (input in this case) it will give you headaches — Mr. E
– Mr. E, Commented Jan 26, 2016 at 13:56

Chris Lawlor · Accepted Answer · 2016-01-26 13:52:43Z

2

If you are using Python 3.3 or newer, you want the yield from statement:

def combs(idx,array,current=[]):
    for item in array[idx]:
        current_copy = current[:]
        current_copy.append(item)
        if idx + 1 < len(array):
            yield from combs(idx+1,array,current_copy)
        else:
            yield current_copy

On Python 2.7, you can expand the yield from into a loop:

def combs(idx,array,current=[]):
    for item in array[idx]:
        current_copy = current[:]
        current_copy.append(item)
        if idx + 1 < len(array):
            for i in combs(idx+1,array,current_copy):
                yield i
        else:
            yield current_copy

edited Jan 26, 2016 at 13:52

answered Jan 26, 2016 at 13:49

Chris Lawlor

49.4k11 gold badges52 silver badges71 bronze badges

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

5 Comments

KevinShaffer Over a year ago

I am using 2.7, is there a similar alternative?

Chris Lawlor Over a year ago

you should be able to loop over the recursive combs call, and yield individual values

KevinShaffer Over a year ago

I have tried doing exactly what I have above, except switching the print current_copy to yield current_copy, and I get no output.

KevinShaffer Over a year ago

So I see that it works, but I'm confused as to why I need to loop over the recursive function call, can you explain that a little bit?

Chris Lawlor Over a year ago

Calling combs just gives you a generator object, you have to loop over it to get the values out of it. It's not like calling a regular function that returns a value. yield from is just syntactic sugar for consuming an iterable (like a generator) and yielding the values.

glibdud · Accepted Answer · 2016-01-26 13:54:07Z

2

Another option for this task is the itertools.product function:

>>> from itertools import product
>>> input = [[-1,2],[-3,4],[-5,6]]
>>> list(product(*input))
[(-1, -3, -5), (-1, -3, 6), (-1, 4, -5), (-1, 4, 6), (2, -3, -5), (2, -3, 6), (2, 4, -5), (2, 4, 6)]

answered Jan 26, 2016 at 13:54

glibdud

7,9704 gold badges32 silver badges38 bronze badges

3 Comments

KevinShaffer Over a year ago

This is great and solves the overall problem at hand! I still am curious as to why what I was trying to do isn't working though :(

Mr. E Over a year ago

If he wants the generator should do myGenerator = product(*myInput).

glibdud Over a year ago

@Mr.E Correct, I used list() to demonstrate the result.

Collectives™ on Stack Overflow

Python Recursive Generator

2 Answers 2

5 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related