[알고리즘 기초] 파이썬 부분집합 알고리즘 (비트연산자)

비트연산자를 이용해서 부분집합을 만들어보았다 (아주 헷 갈 림)

 

arr = [3,6]
n = len(arr)

for i in range(1<<n):
    for j in range(n):
        if i&(1<<j): #i의 j번째 비트가 1이면 j번째 원소 출력
            print(arr[j],end=' ')
    print()

 

arr 에 집합을 받아온다 

n 은 집합 요소의 개수 (len)

 

a << n  

a  *  (2의 n승)

 

& : and 연산 (둘다 1일때 1)

ex) a = 3 (0011)  b = 5 ( 0101 )   ==> a&b = 1 (0001)

 

i 는 총 부분집합의 개수 (2^n) 만큼 실행된다 0000 , 0001 , 0010 , 0011 이 순서

j 는 0,1 이 들어가고 if 문의 (1<<j) 는 2^0(1)  2^1(2)  따라서 0001 0010  이렇게 두개가된다

 

if 문의 i&(1<<j) 는

0000 0001  == 0000

0000 0010 == 0000

 

0001 0001 == 0001  (0번째자리가 1)

0001 0010 == 0000

 

0010 0001 == 0000

0010 0010 == 0010 (1번째 자리가 1)

 

0011 0001 == 0001 (0번쨰 자리가 1)

0011 0010 == 0010 (1번째 자리가 1) 

 

따라서 

 

(공백)

3

6

3 6

 

이 출력된다 !