アイテムのリストがあり、可能なすべてのサブセットを生成したいと思います。したがって、アイテム番号と選択したすべてのアイテムのリストをパラメーターとして使用する再帰関数を使用しています。この関数は、最初のパラメーターとして0を指定して呼び出され、次のことを行います。
- インデックスパラメータで記述されたアイテムを調べます
- それを選択します
- インクリメントされたインデックスパラメータで自分自身を呼び出します
- アイテムの選択を解除します
- インクリメントされたインデックスパラメータで自分自身を呼び出します
何かを最適化するために可能なサブセットが必要ですが、リストが非常に長くなるため、すべてを見ることができません。最初は、ブルートフォースを使用してすべてのサブセットを考慮に入れようとしましたが、それは単純なアイデアでした。新しい計画は、最初の「有用な」選択を行う欲張りアルゴリズムを作成することです。自分のニーズに合ったサブセットが見つかり、Pythonのyieldステートメントが正確に正しい選択であると判断するまで、すべてのサブセットを調べたいと思います。ここにいくつかのコードがあります:
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
出力は次のとおりです:何も
最初はサブセットの生成でエラーが発生したと思いましたが、if条件では、コメント付きのprintステートメントがあることがわかります。このprintステートメントのコメントを外し、代わりにyieldステートメントをコメントアウトすると、可能なすべての選択肢が出力され、forループが壊れます。
yieldステートメントを使用すると、コードはエラーなしで実行されますが、何も実行されません。