how to use python's yield statement

Question

I have a list of items and would like to generate all possible subsets. Therefore I'm using a recursive function with the item number and a list of all selected items as parameters. The function is called with 0 as the first parameter and does the following:

It looks at the item described by the index parameter
It selects it
It calls itself with an incremented index parameter
It deselects the item
It calls itself with an incremented index parameter

I'm needing the possible subsets to optimise something but since the list will get very long, I can't look at all of them. At first I tried to use brute force to take all subsets into consideration but that was a naive idea. Now the new plan is to create a greedy algorithm that takes the first "useful" selection: I want to look at all subsets until I find one that suits my needs and figured that python's yield statement is exactly the right choice. Here's some code:

def bruteForceLeft(selected,index):
    #left is the list of which i need subsets
    #its a gobal variable. to test the code, just make sure that you have a 
    #list called left in scope
    if index==len(left):
        #print(selected)
        yield selected
    else:
        #the algorithm stores the selection in a tuple of two lists
        #that's necessary since there's a second list called right as well
        #I think you can just ignore this. Think of selected as a list that
        #contains the current selection, not a tuple that contains the current
        #selection on the right as well as the left side.
        selected[0].append(left[index])
        bruteForceLeft(selected,index+1)
        selected[0].pop()
        bruteForceLeft(selected,index+1)

#as you can see I pass a tuple of two empty lists to the function.
#only the first one is used in this piece of code
for option in bruteForceLeft( ([],[]) ,0):
    print(option)
    #check if the option is "good"
    #break

The output is: nothing

At first I thought that I had made an error in generating the subsets, but in the if condition you can see that I have a commented print statement. If I uncomment this print statement and instead comment out the yield statement all the possible choices are printed - and the for loop is broken

With the yield statement the code runs without error, but it doesn't do anything either.

I still don't understand what the input/output of this should be. — Aesthete
– Aesthete, Commented Nov 29, 2012 at 21:44
This doesn't reply to your question, but unless you're doing this as an exercise, it's probably worth to check itertools.combinations. All subsets would be the union of the combinations of length(1) to length(n), I believe — loopbackbee
– loopbackbee, Commented Nov 29, 2012 at 21:52
only the single most popular python question ever!? The Python yield keyword explained — John Mee
– John Mee, Commented Nov 29, 2012 at 22:23

Xymostech · Accepted Answer · 2012-11-29 21:42:32Z

4

The problem is that when you recursively call bruteForceLeft, the yielded values don't magically get yielded from the enclosing function. So, you need to re-yield them yourself:

def bruteForceLeft(selected,index):
    #left is the list of which i need subsets
    if index==len(left):
        #print(selected)
        yield selected
    else:
        #the algorithm stores the selection in a tuple of two lists
        #that's necessary since there's a second list called right as well
        #I think you can just ignore this. Think of selected as a list that
        #contains the current selection, not a tuple that contains the current
        #selection on the right as well as the left side.
        selected[0].append(left[index])
        for s in bruteForceLeft(selected,index+1):
            yield s
        selected[0].pop()
        for s in bruteForceLeft(selected,index+1):
            yield s

(Edit: I actually just tested this, and your code has errors, but I'm pretty sure not re-yielding is the problem)

answered Nov 29, 2012 at 21:42

Xymostech

9,8803 gold badges36 silver badges45 bronze badges

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

3 Comments

lhk Over a year ago

hm, i can accept an answer in 6 minutes - i guess we have to wait

Xymostech Over a year ago

Okay. Do you perchance have a global variable left or something? I'm really confused how this code works. (it's throwing errors when I run it)

lhk Over a year ago

yep. left is a global variable. I thought the comments had documented this, but you're right. they only say that left is a list. i'll edit that

Collectives™ on Stack Overflow

how to use python's yield statement

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related