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.
