[Algorithm] Binary Counting - 비트연산을 통한 순열(부분집합, power set) 구하기

프로그래밍을 하다보면, 모든 경우의 수를 확인해야 하는 경우가 생기는데,
이럴경우 각 원소에 대한 모든 부분집합을 구해서 확인해야 한다.

1, 2, 3에 대해서 본다면 아래와 같은 모든 부분 집합이 존재 한다.
(1), (2), (3), (1 2), (1 3), (2 3), (1 2 3)

이러한 부분집합을 구할때 간단히 비트연산을 이용해서 구할 수 있는 방법이 있다.

A, B, C, D에 대한 부분 집합 

1 2 3 4 5 6 7 8 9 10 11 12 13 14

void main(void){     int i, j;     char arr[4] = { 'a', 'b', 'c', 'd' };     int n = 4;     for (i = 0; i < (1 << (n)); i++){         for (j = 0; j < n; j++){             if (i & (1 << j)){                 printf("%c ", arr[j]);             }         }         printf("\n");     } } Colored by Color Scripter

cs

위 비트연산 1<<(n) 과, i & (1<<j) 에 대한 설명은 ->여기로<-

원소 수에 해당하는 N개의 비트열을 이용한다.

N번째 비트값이 1이면 N번째 원소가 포함되었음을 의미한다.

4비트에서 하나씩 증가 했을때의 자리수로 아래와 같이 출력됨.

10 진수	이진수	{A, B, C, D}
0	0000
1	0001	A
2	0010	B
3	0011	B, A
4	0100	C
5	0101	C, A
6	0110	C, B
7	0111	C, B, A
8	1000	D
9	1001	D, A
10	1010	D, B
11	1011	D, B, A
12	1100	D, C
13	1101	D, C, A
14	1110	D, C, B
15	1111	D, C, B, A