멱집합 powerset

멱집합은 집합의 모든 부분집합이다. {a, b}가 있으면 {}, {a}, {b}, {a,b} 가 멱집합이다.

원소 a를 하나 빼고 나머지 원소들로 부분집합 A를 만들고 a와 A를 합한 것, a가 없고 A만 있는 것을 찾아내면 된다.

원소가 있는지 없는지에 따라 트리를 만들면 저런 모양이 된다. 리프 노드를 보면 {}, {a}, {b}, {a,b}가 있으므로 멱집합이 완성된다.

왼쪽 가지와 오른쪽 가지를 include[k] = True, include[k] = False로 표현했다. True면 해당 인덱스의 원소가 있는 것이고 False면 해당 원소를 제외하고 부분 집합을 만드는 것이다. 계속 돌리다보면 공집합부터 모든 원소가 있는 집합이 만들어진다. include의 인덱스 i가 True라면 arr에서 해당 인덱스 i의 원소가 사용되고 False인 인덱스는 사용되지 않는다.

arr = ['a','b','c','d']
n = len(arr)
include = [0 for i in range(n)]
def power(k):
    if k==n:
        print('{',end='')
        for i in range(n):
            if include[i]:print(arr[i],end='')
        print('}')
        return True
    include[k]=True
    power(k+1)
    include[k]=False
    power(k+1)
power(0)

출력은 다음과 같다.

{abcd}

{abc}

{abd}

{ab}

{acd}

{ac}

{ad}

{a}

{bcd}

{bc}

{bd}

{b}

{cd}

{c}

{d}

{}