冪集合の作成(Python3)

Question

リストを受け取り、冪集合を出力する関数を作成したのですが、期待する出力結果を得られません。
コードは以下の通りです。

def power_set(item_lists):
    
    p_sets = [[]]

    for item in item_lists:
        new_p_sets = p_sets.copy()
        for element in new_p_sets:
            element.append(item)
        p_sets = p_sets + new_p_sets
    
    return p_sets

例をあげると、power_set([1,2,3])を実行すれば

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

が出力されるはずなのですが、出力された結果は

[[1, 2, 2, 3, 3, 3, 3],
[1, 2, 2, 3, 3, 3, 3],
[1, 2, 2, 3, 3, 3, 3],
[1, 2, 2, 3, 3, 3, 3],
[1, 2, 2, 3, 3, 3, 3],
[1, 2, 2, 3, 3, 3, 3],
[1, 2, 2, 3, 3, 3, 3],
[1, 2, 2, 3, 3, 3, 3]]

でした。コードの間違っている点を指摘していただけると幸いです。

Answer 1

外側のリストはコピーされるかもしれませんが、内側のelementは最初に書いた1つしかないままなので、そうなります。

こんな感じで書くと良いんじゃないでしょうか。

def power_set(item_lists):

    p_sets = [[]]

    for item in item_lists:
        tmp = []
        for element in p_sets:
            tmp.append(element + [item])
        p_sets.extend(tmp)

    return p_sets
print(power_set([1,2,3]))
# => [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Comments

[退会済みユーザー]

すみません、"内側のelementは最初に書いた1つしかないまま" とはどういうことでしょうか？

[hayataka2049]

p_sets.copy()でcopyされるのは外側のlistだけで、内側の[]は参照がコピーされるだけです。
for element in new_p_sets:
element.append(item)
p_sets = p_sets + new_p_sets
elementは常に同じものを参照しているので、1が1回、2が2回、3が3回というlistになります（結果の子リストも言うまでもないですがすべて同じlistへの参照です）

[退会済みユーザー]

理解できました！ありがとうございます！！

Answer 2

全ての組み合わせを返すイテレータcombinationsを使ったジェネレータとしてこうも書けるのかな。

from itertools import combinations

def power_set(items):
    n = len(items)
    for i in range(n+1):
        yield from combinations(items, i)

print(list(power_set([1,2,3])))

Comments

[退会済みユーザー]

ありがとうございます！

Answer 3

y.py

p_sets = []

n = 3
for i in range(2 ** n):
  lst = [x + 1 for x in range(i) if 2 **x & i]
  p_sets.append(lst)


print(sorted(p_sets, key=lambda x: len(x)))

実行例

求める集合の要素の数は 2 ＊＊ n です。
数字 0 から 2 ＊＊ n - 1 に対応する要素を次のようにして求めます。

• 数字を 2 進数で表したときの 1, 0 が、要素に含まれている/いない

Comments

[退会済みユーザー]

なるほど、ビット演算を使うとだいぶスッキリと書けますね。ありがとうございます！