[자료구조/알고리즘] 비트연산을 통한 순열

[Algorithm] Binary Counting - 부분집합, power set 구하기

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");

    }

}

1<<n

• 2n의 값을 갖는다.
• 원소가 n개일 경우의 모든 부분집합의 수를 의미한다.
• Power set(모든 부분 집합)
  -공집합과 자기 자신을 포함한 모든 부분집합
  -각 원소가 포함되거나 포함되지 않는 2가지 경우의 수를 계산하면 모든 부분집합의 수가 계산된다.

i & (1 << j)

• 계산 결과는 i의 j번째 비트가 1인지 아닌지를 의미한다.

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