바이너리 카운팅을 이용한 부분집합 구현과 재귀함수를 이용한 조합 구현하기

1. 부분집합 생성하기

 

비트 연산

 

1<<n은 비트 0000000....1을 왼쪽으로 n번 shift 했다는 소리

 

 

그래서 1<<n 자체로 $2^{n}$을 나타낸다

 

원소가 n개인 부분집합의 개수는 $2^{n}$개인데, 0부터 $2^{n}-1$까지를 2진수로 나타낸다면,

 

예를 들어 n=4이면 0부터 15까지가 0000, 0001, 0010, 0011, ..., 1111으로 나타난다

 

이 비트자체가 하나의 부분집합이라고 볼 수 있다. 

 

무슨 말이냐면 원소의 개수가 n=4인 집합 {a,b,c,d}의 부분집합은..

 

(오른쪽에서) i번째 비트값이 1이면 {a,b,c,d}에서 해당하는 i번째 위치의 원소를 선택하는 것으로 구할 수 있다

 

예를 들어 0010은 1번째 비트값이 1이므로 {a,b,c,d}에서 1번째 원소인 b를 선택한 {b}를 나타내고

 

0110은 1번째, 2번째 비트값이 1이므로 {a,b,c,d}에서 {b,c}를 나타낸다고 생각할 수 있다

 

 

비트 연산의 &연산은 해당하는 비트가 1인지 아닌지 검사하는 특징이 있다

 

왜냐하면 1과 1의 and연산은 1이기 때문이다

 

 

그러므로 i & (1<<j)에 대해 생각해본다면, 1 << j는 00000000000000000.....1에서 맨 오른쪽에 있는 1을 j번 왼쪽으로 shift한 값이다.

 

이것과 이진수로 나타낸 어떤 i = 0000111110110101010101011100...1과 and연산을 수행한다면??

 

i의 j번째 bit가 1인지 아닌지를 검사한다

 

arr = [3,6,7]

n = len(arr) ##배열의 길이

for i in range(1<<n): ##i는 arr의 모든 부분집합
    
    partial = [] ##i를 나타내는 부분집합
    
    for j in range(n): ##i를 길이 n인 이진수로 나타낼때, 0~n-1의 비트 검사
        
        if i & (1<<j): #i의 j번째 bit가 1이면...
            
            partial.append(arr[j]) ##j번째 원소는 i가 나타내는 부분집합의 원소
        
    print(partial)

[]
[3]
[6]
[3, 6]
[7]
[3, 7]
[6, 7]
[3, 6, 7]

 

 

2. 다중for문으로 단순히 조합 구현

 

5개 [1,2,3,4,5]중에서 3개를 고르는 조합은 어떻게 구할 수 있을까??

 

3개의 index i,j,k를 배열 내에서 움직이면서 찾을 수 있는데

 

중복된 원소를 고르지 않는다고 생각하면

 

 

첫번째 원소 i는 1,2,3까지 가능하다. j,k가 최소한 한자리는 차지해야하니까.. 최대 3,4,5쪽 까지 이동가능하거든

 

1,2,3중에서 i가 하나를 뽑았다면, j는 i+1부터 4까지 가능할 것이다.

 

i,j가 각각 뽑았다면, k는 i,j가 뽑지 않은 j+1부터 5까지 가능할 것이다.

 

#조합 단순 구현하기

N = 5

for i in range(1,N-1):
    
    for j in range(i+1,N):
        
        for k in range(j+1,N+1):
            
            print(i,j,k)

 

 

3. 재귀함수를 이용한 조합 구현

 

많은 경우 임의의 n개에서 임의의 r개를 고르는 조합을 원한다

 

그럴 때마다 r이 얼마일지도 모르는데 r개의 for문을 다중으로 쓸 수는 없다

 

def nCr(n,r,s):
    
    if r == 0:
        
        print(*comb)
    
    else:
        
        for i in range(s,n-r+1):
            
            comb[r-1] = A[i]
            
            nCr(n,r-1,i+1)

A = [1,2,3,4,5]

n = len(A)

r = 3

comb = [0] * r

nCr(n,r,0)

3 2 1
4 2 1
5 2 1
4 3 1
5 3 1
5 4 1
4 3 2
5 3 2
5 4 2
5 4 3

 

5개 중에서 3개를 뽑는 조합.. comb = [0,0,0]에 3개의 수를 A = [1,2,3,4,5]에서 뽑아서 채워 넣는 방법

 

먼저 comb[2]에 for i in range(0,3):을 순회하여.. A[0] = 1이 들어가고..

 

r=2, i = 1인 상태로 nCr에 들어간다

 

다음 comb[1]에 for i in range(1,4):을 순회하여... A[1]=2이 들어간다..

 

r=1, i=2인 상태로 nCr에 들어간다

 

다음 comb[0]에 for i in range(2,5)을 순회하여 A[2] = 3이 들어간다..

 

r=0, i=3인 상태로 들어가는데... r=0이므로 comb = [3,2,1]이 완성된다

 

-----------------------------------------------------

 

그러면 다시 뒤로 돌아가서

 

""comb[0]에 for i in range(2,5)을 순회하여 A[2] = 3이 들어간다..""

 

이제 i = 3 시작.. comb[0]에 A[3] = 4가 들어간다

 

comb = [4,2,1]이 되고 r=0, i=4인 상태로 다음 재귀로 들어감. r=0이면 comb를 출력

 

그 후 다시 되돌아감

 

""comb[0]에 for i in range(2,5)을 순회하여 A[2] = 3이 들어간다..""

 

이제 i = 4 시작.. comb[0]에 A[4] = 5가 들어간다

 

comb = [5,2,1]이 되고 r=0, i=5인 상태로 들어가는데.. r=0이 되므로 comb를 출력

 

그 후 다시 되돌아가

 

""comb[0]에 for i in range(2,5)을 순회하여 A[2] = 3이 들어간다..""는 모든 for문을 순회해서 더 되돌아가

 

""다음 comb[1]에 for i in range(1,4):을 순회하여... A[1]=2이 들어간다..""

 

여기서 i=1이 끝났으니까 i=2 시작

 

comb[1]에 A[2] = 3이 들어가서.. comb[0,3,1]인 상태로 r=1, i=3인 상태가 다음 재귀로 들어감

 

다음 "comb[0]에 for i in range(3, 5):를 순회하면서... A[3]=4가 가 들어감"

 

그래서 comb = [4,3,1]이 완성되고 r=0, i=4인 상태로 다음 재귀로 들어가는데 r=0이므로 comb 출력..

 

.... 위 재귀를 계속 반복해서...

 

 

 

4. 재귀를 이용한 중복조합 구현

 

그렇다면.. 중복조합은 어떻게 구현할까?

 

위의 재귀 반복을 이해했다면 응용해서 가능하다

 

i에서 A[i]를 뽑고 다음 i+1로 이동한것은 i번은 다음에는 뽑지 않겠다는 것이다.

 

그렇다면 다음에도 i를 뽑을 수 있도록 만들면 된다

 

그리고 i의 범위가 문제인데

 

for i in range(s,n-r+1):은 i가 선택할 수 있는 범위를 나타내는 것이었다

 

r에 상관없이 i의 범위를 항상 s~n으로 해둔다면?

 

def nHr(n,r,s):
    
    if r == 0:
        
        print(*comb)
    
    else:
        
        for i in range(s,n):
            
            comb[r-1] = A[i]
            nHr(n,r-1,i)

A = [1,2,3,4,5]

n = len(A)

r = 3

comb = [0] * r

nHr(n,r,0)

1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
2 2 1
3 2 1
4 2 1
5 2 1
3 3 1
4 3 1
5 3 1
4 4 1
5 4 1
5 5 1
2 2 2
3 2 2
4 2 2
5 2 2
3 3 2
4 3 2
5 3 2
4 4 2
5 4 2
5 5 2
3 3 3
4 3 3
5 3 3
4 4 3
5 4 3
5 5 3
4 4 4
5 4 4
5 5 4
5 5 5

 

그러면 처음에 comb[2]에 A[0]을 뽑고.. for i in range(0,5):를 순회할건데..

 

다음에 comb[1]에.. i=0인 상태로 들어가므로 A[0]을 뽑고 for i in range(0,5)를 순회할거고

 

다시 comb[0]에 i=0인 상태로 들어가고.. A[0]을 뽑고 for i in range(0,5)를 순회할거고..

 

comb = [1,1,1]이 완성되어 출력

 

뒤로 돌아가서 i=1인 상태에서 comb[0]에 A[1]을 뽑아서 [2,1,1]을 완성하여.. comb = [2,1,1]을 출력

 

다시 돌아가서.. [3,1,1], [4,1,1], [5,1,1]을 출력하고..

 

"다시 comb[0]에 i=0인 상태로 들어가고.. A[0]을 뽑고 for i in range(0,5)를 순회할거고.."여기가 끝..

 

더 되돌아가서..

 

""comb[1]에.. i=0인 상태로 들어가므로 A[0]을 뽑고 for i in range(0,5)를 순회할거고""에서 i=1이 시작되어

 

comb = [0,2,1]이고 i=1인 상태로 들어감

 

-----------------------------------------------------------

[1,2,1]도 가능한거 아니야?? 아니 조합은 [2,1,1]과 [1,2,1]은 같은거잖아

-----------------------------------------------------------

 

그러면 comb[0]에 A[1]을 뽑고 for i in range(1,5)를 순회...

 

이를 계속 반복하면.. 이것이 중복조합