Generator - how to use python39s yield statement

De openkb
Aller à : Navigation, rechercher

Sommaire

Questions

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.

Answers

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)

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/13635237/how-to-use-pythons-yield-statement

Related

Outils personnels
Espaces de noms

Variantes
Actions
Navigation
Outils