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, Nov 29 '12 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](http://docs.python.org/2/library/itertools.html#itertools.combinations). All subsets would be the union of the combinations of length(1) to length(n), I believe — loopbackbee, Nov 29 '12 at 21:52
only the single most popular python question ever!? [The Python yield keyword explained](http://stackoverflow.com/questions/231767/the-python-yield-keyword-explained) — John Mee, Nov 29 '12 at 22:23

score 4 · Accepted Answer · answered Nov 29 '12 at 21:42

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)

hm, i can accept an answer in 6 minutes - i guess we have to wait — lhk, Nov 29 '12 at 21:48
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) — Xymostech, Nov 29 '12 at 21:50
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 — lhk, Nov 29 '12 at 21:51

how to use python's yield statement

1 Answers1