[Algorithm] 부분집합

• 집합에 포함된 원소들을 선택하는 것
• 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 거임
• N개의 원소를 포함한 집합의 부분 집합 (공집합 포함) == 2^N개

바이너리 카운팅을 통한 사전적 순서

• 부분집합을 생성하기 위한 가장 자연스러운 방법
• 사전적 순서로 생성하기 위한 가장 간단한 방법

Binary counting

• 원소 수에 해당하는 N개의 비트열을 이용
• n번째 비트 값이 1이면 n번째 원소가 포함되었음을 의미
  

# 재귀를 통한 구현
def func(s,e):
    if s == e:
        for i in range(N):
            if bit[i]:
                print(A[i], end = ' ')
        print()
    else:
        bit[s] = 1
        func(s+1,e)
        bit[s] = 0
        func(s+1,e)

A = [7,3,5,3,4]
N = len(A)
bit = [0]*N # bit[i] A[i]원소가 부분집합에 포함되는지 표시함
func(0,N)

# bit연산을 통한 구현
arr = [3,6,7,1,5,4]
n = len(arr)

for i in range(0,(1<<n)): # 부분집합의 개수
    for j in range(0,n): # 원소의 수만큼 비트 비교
        if i & (1<<j): # i의 j번째 비트가 1 이면 j번째 원소 출력
            print(arr[j], end = ' ')
    print()