[Python] right shift와 powerSet

가능한 모든 서브셋의 집합인 파워셋을 만들려다가 아래와 같은 코드를 발견했다.

def powerSet(items):
    temp = []
    N = len(items)
    for i in range(2**N): 
        combo = []
        for j in range(N):
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        temp.append(combo)
    
    return temp

[출처] stackoverflow.com/questions/16309441/struggling-to-understand-bitwise-operators-in-python

 

 

1. 산술 시프트?

    비트연산의 한 종류로, 8 >> 1이라면 이진법으로 표현된 8(1000)을 오른쪽으로 한칸 밀어서 4( 100)가 되는 연산을 가리킨다.

아래 그림은 23(10111)을 오른쪽으로 한칸 밀어서 11( 1011)가 되는 경우.

(밀어서 생기는 빈 공간은 기존 최상위비트를 따라간다고 한다)

 

 

 

2. 산술 시프트가 왜 파워셋 만들기에 사용되지?

    10번째 줄에 print(i, j, i >> j, items[j], combo)를 끼워넣고 powerSet([1, 2, 3])을 실행해보았다.

 

0    0    0    1    []
0    1    0    2    []
0    2    0    3    []
1    0    1    1    [1]
1    1    0    2    [1]
1    2    0    3    [1]
2    0    2    1    []
2    1    1    2    [2]
2    2    0    3    [2]
3    0    3    1    [1]
3    1    1    2    [1, 2]
3    2    0    3    [1, 2]
4    0    4    1    []
4    1    2    2    []
4    2    1    3    [3]
5    0    5    1    [1]
5    1    2    2    [1]
5    2    1    3    [1, 3]
6    0    6    1    []
6    1    3    2    [2]
6    2    1    3    [2, 3]
7    0    7    1    [1]
7    1    3    2    [1, 2]
7    2    1    3    [1, 2, 3]

 

i >> j 결과에 따라 홀수면 추가, 짝수면 패스해가며 원소를 추가하고 있다. i 한 턴에 3줄씩 표시되니까 좀 정신이 없다. j 루프문을 한 줄에 표시되게 하고, i >> j 결과만 출력되게 해보자.

def powerSet(items):
    N = len(items)
    for i in range(2**N): 
        combo = []
        print(i, end="\t")
        for j in range(N):
            if (i >> j) % 2 == 1:
                combo.append(items[j])
            print(i >> j, end = "\t")
        print("\n")

 

뭔가 규칙성이 보이는 것 같다.

 

0     0    0    0
1     1    0    0
2     2    1    0
3     3    1    0
4     4    2    1
5     5    2    1
6     6    3    1
7     7    3    1

 

보기 좋게 홀수를 1, 짝수를 0으로 바꾸면 아래와 같은 결과가 나온다.

 

0    0    0    0
1    1    0    0
2    0    1    0
3    1    1    0
4    0    0    1
5    1    0    1
6    0    1    1
7    1    1    1

 

리스트가 4개짜리라면 이렇게 된다.

 

00    0    0    0    0
01    1    0    0    0
02    0    1    0    0
03    1    1    0    0
04    0    0    1    0
05    1    0    1    0
06    0    1    1    0
07    1    1    1    0
08    0    0    0    1
09    1    0    0    1
10    0    1    0    1
11    1    1    0    1
12    0    0    1    1
13    1    0    1    1
14    0    1    1    1
15    1    1    1    1

 

산술시프트 연산으로 포함은 1, 미포함은 0으로 표를 만든 다음 리스트 원소에 적용한 것이라고 보면 될 것 같다. 각 i번째 줄은 i의 이진법 표기를 뒤집어놓은 것처럼 생겼는데, 맨앞에 오는 원소를 제일 먼저 포함하는 게 유리하기 때문에 % 2 == 0이 아니라 % == 1을 택한 걸까?

 

3. 2**N이 3**N이 된다면

    파워셋을 가방이라고 본다면 담기/안 담기의 2가지 경우의 수가 있을 수 있다.

만약 가방이 2개라면 3**N이 될 거고, 안 담기/가방 1에 담기/가방 2에 담기가 가능하다.

N = 3
items = [1, 2, 3]
for i in range(3**N):
    combo, combo2 = [], []
    print(i, end="\t")
    for j in range(N):
        if (i // 3**j) % 3 == 1:
            print(1, end="\t")
        elif (i // 3**j) % 3 == 0:
            print(2, end="\t")
        else:
            print(0, end="\t")
    print("\n")

 

00    2    2    2
01    1    2    2
02    0    2    2
03    2    1    2
04    1    1    2
05    0    1    2
06    2    0    2
07    1    0    2
08    0    0    2
09    2    2    1
10    1    2    1
11    0    2    1
12    2    1    1
13    1    1    1
14    0    1    1
15    2    0    1
16    1    0    1
17    0    0    1
18    2    2    0
19    1    2    0
20    0    2    0
21    2    1    0
22    1    1    0
23    0    1    0
24    2    0    0
25    1    0    0
26    0    0    0