멱집합 구하기

획기적인 방법이 있다 바로 비트마스크를 이용하는 방법이다 (나는 정말 획기적이라고 느꼈다.)

예를들면 원소의개수가 3개 (a, b, c)가 있다치면

이걸 비트마스크로 표현하면

000 // 공집합

001 // c

010 // b

011 // b, c

100 // a

101 // a, c

110 // a, b

111 // a, b, 

이런식으로 모든 부분집합 즉 멱집합을 구할수 있다

소스코드

def powerset(s): #배열생성이 generate 방식이다
    x = len(s)
    masks = [1 << i for i in range(x)]
    print(masks)
    for i in range(1, 1 << x):
        print([(ss,mask) for mask, ss in zip(masks, s) if i & mask])
        yield [ss for mask, ss in zip(masks, s) if i & mask]