pythonで、冪集合 powersetのiteratorを作る

べき集合(powerset)とは

リストaがあったとする。

a = [1, 2, 3,]

これを集合と見たてたとき、その全ての部分集合は

() (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)

である。

$2^a$ = {aの全ての部分集合（上のやつら）}

を aの 冪集合(powerset)　という。

べき集合のiteratorの実装

from itertools import chain,combinations
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

iterableに上のlist aなどをいれて使う。

注意

べき集合は　全ての組合せ、全ての順列とは違う 。
曖昧であれば、それぞれの定義と具体例を再確認されたい。

ちなみに、組合せと順列のiteratorはitertoolsに備わっている。

参考

python official itertools recipes