0

アイテムのリストがあり、可能なすべてのサブセットを生成したいと思います。したがって、アイテム番号と選択したすべてのアイテムのリストをパラメーターとして使用する再帰関数を使用しています。この関数は、最初のパラメーターとして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ステートメントを使用すると、コードはエラーなしで実行されますが、何も実行されません。

4

1 に答える 1

4

問題は、 を再帰的に呼び出すbruteForceLeftと、生成された値が、囲んでいる関数から魔法のように生成されないことです。したがって、それらを自分で再生成する必要があります。

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

（編集：実際にこれをテストしたところ、コードにエラーがありますが、再生成が問題ではないことは確かです）

于 2012-11-29T21:42:32.913 に答える