[파이썬] 부분집합을 구하는 방법

부분집합 구하는 방법

부분집합의 수

• 각 원소가 n개 일 때, 공집합을 포함한 부분집합의 수는 2^n개
• ex) [1,2,3,4,5] —> 2^5 = 32개

각 원소가 부분 집합에 포함되었는지 확인하는 방법

arr = [1,2,3,4,5]
for i in range(2) :
    arr[0] = i
    for j in range(2) :
        arr[1] = j
        for k in range(2) :
            arr[2] = k
            for l in range(2) :
                arr[3] = l
                for n in range(2) :
                    arr[4] = n
                    print(arr)

반응형

부분집합을 for문을 이용하는 방법(비트 연산자 활용)

비트연산자

• & : 비트 단위로 and 연산
• | : 비트 단위로 or 연산
• << : 피연산자의 비트 열을 왼쪽으로 이동
• >>피트연산자의 비트 열을 오른쪽으로 이동

arr = [1,2,3,4,5,6]

n = len(arr)

for i in range(1<<n): #부분 집합의 개수
    result = []
    for j in range(n) : # 원하는 수만큼 비트를 비교
        if i & (1<<j): # i 의 j번째 비트가 1인지 아닌지 검사
            result.append(arr[j])
    print(result)