ビットで部分集合の列挙

配列aのインデクスiに対してある数nのi番目のビットが立っているかどうかを[0,2^n-1]に対して調べれば部分集合を列挙できると気がついた。

>>> a = range(4)
>>> for n in range(2**len(a)):
...     [a[i] for i in xrange(len(a)) if (n >> i) & 1 == 1]
...
[]
[0]
[1]
[0, 1]
[2]
[0, 2]
[1, 2]
[0, 1, 2]
[3]
[0, 3]
[1, 3]
[0, 1, 3]
[2, 3]
[0, 2, 3]
[1, 2, 3]
[0, 1, 2, 3]
>>>

def subset(a):
    for n in range(2**len(a)):
        yield [a[i] for i in xrange(len(a)) if (n >> i) & 1 == 1]