私の再帰的なPythonソリューションは、回答リストの現在のすべての項目を追加して現在のリストに置き換えています。

Question

プログラミングの質問 の整数配列内のすべての部分集合を見つけるPythonソリューションを実装しようとしています。重複のない整数配列のすべてのサブセットを含む配列 を返し、 をソートする必要があります。

def subsetHelper(cur_set, index, A, ans): 
    if index >= len(A): 
     print "appending ", cur_set 
     ans.append(cur_set) 
     print "ans: ", ans 
     return 
    # don't include current number 
    subsetHelper(cur_set, index+1, A, ans) 

    # include current number 
    cur_set.append(A[index]) 
    subsetHelper(cur_set, index+1, A, ans) 
    cur_set.pop() 

def subsets(A): 
    A.sort() 
    ans = [] 
    cur_set = [] 
    # dont include current number 
    subsetHelper(cur_set, 0, A, ans) 
    return ans 

この同じロジックをC++で実装すると、正しい戻り値が得られます。しかし、私がPythonでこれを行うと、最後に空リストのコレクションが得られますが、反復処理中は、リスト内のすべてのアイテムに同じ現在のリストがコピーされます。 。なぜこうなった？ここでは、出力は次のようになります。

print subsets([1,2,3]) 
appending [] 
ans: [[]] 
appending [3] 
ans: [[3], [3]] 
appending [2] 
ans: [[2], [2], [2]] 
appending [2, 3] 
ans: [[2, 3], [2, 3], [2, 3], [2, 3]] 
appending [1] 
ans: [[1], [1], [1], [1], [1]] 
appending [1, 3] 
ans: [[1, 3], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3]] 
appending [1, 2] 
ans: [[1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2]] 
appending [1, 2, 3] 
ans: [[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]] 
[[], [], [], [], [], [], [], []] 

Answer 1

2の問題がここにあります。問題は、まずあなたans.extend代わりのans.appendは、かつて我々が最後に空のリストである第二の問題を取得し、その理由は、そのAPPENDであることを変更することですリストansにcur_setへの参照を追加すると、再帰の過程ですべての要素が削除されるので、最後に空の同じリストへの参照がいくつか残ってしまいます。これを修正するには、リストの現在の内容のコピーを例えばlist(cur_set)とする。

また、このクラス

def subsetHelper(cur_set, index, A, ans): 
    if index >= len(A): 
     print "appending ", cur_set 
     ans.append(list(cur_set)) # <--- here was the problem 
     print "ans: ", ans 
     return 
    # don't include current number 
    subsetHelper(cur_set, index+1, A, ans) 

    # include current number 
    cur_set.append(A[index]) 
    self.subsetHelper(cur_set, index+1, A, ans) 
    cur_set.pop() 

def subsets(A): 
    A.sort() 
    ans = [] 
    cur_set = [] 
    # dont include current number 
    subsetHelper(cur_set, 0, A, ans) 
    return ans 

テスト

>>> subsets([1,2,3]) 
appending [] 
ans: [[]] 
appending [3] 
ans: [[], [3]] 
appending [2] 
ans: [[], [3], [2]] 
appending [2, 3] 
ans: [[], [3], [2], [2, 3]] 
appending [1] 
ans: [[], [3], [2], [2, 3], [1]] 
appending [1, 3] 
ans: [[], [3], [2], [2, 3], [1], [1, 3]] 
appending [1, 2] 
ans: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2]] 
appending [1, 2, 3] 
ans: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]] 
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]] 
>>> 

Answer 2

問題は、あなたがそうでもcur_setがされた後に呼び出しの間cur_setリストオブジェクトを再使用しているであることを確認する理由はありませんansに追加し、先物をsusetHelperに呼び出すと、依然としてリストが変更されます。具体的には、のコールはリストを空にします。この問題は、正確なオブジェクトの代わりにcur_setのコピーを保存することで解決できます。

def subsetHelper(cur_set, index, A, ans): 
    if index >= len(A): 
     print "appending ", cur_set 
     ans.append(cur_set[:]) 
     print "ans: ", ans 
     return 
    # don't include current number 
    subsetHelper(cur_set, index+1, A, ans) 

    # include current number 
    cur_set.append(A[index]) 
    subsetHelper(cur_set, index+1, A, ans) 
    cur_set.pop() 

def subsets(A): 
    A.sort() 
    ans = [] 
    cur_set = [] 
    # dont include current number 
    subsetHelper(cur_set, 0, A, ans) 
    return ans 

print subsets([12, 13]) 

ここでは、状態ベースのoopおよび機能的なプログラミングスタイルを混在させているわけではありません。原則としてそれには何も問題はありませんが、状態ベースの再帰をデバッグすることは非常にイライラする可能性があります。これが学習の練習であれば、純粋に機能的な方法（再帰的な方法）でこの問題を解決しようとすることをお勧めします。どちらの方法でも問題をよりよく理解できます。