bit演算を使って、冪集合を求めるスクリプト

power_set.py

S = 1 << 1 | 1 << 3 | 1 << 5  # S = {1, 3, 5}
N = 6  # 6ビット使用するため
PS = S  # 集合Sの冪集合PSを求める。
ans = [[]]  # 空集合は含めておく
while PS > 0:
    tmp = []
    for i in range(N):
        if (PS >> i) & 1:
            tmp.append(i)
    ans.append(tmp)
    PS = (PS - 1) & S  # ここの演算が面白い
print(ans)

実行結果

% python power_set.py
[[], [1, 3, 5], [3, 5], [1, 5], [5], [1, 3], [3], [1]]