C언어 멱집합 구하기 : 반복문(iteration)과 재귀(recursion)

집합의 모든 부분집합을 멱집합이라고 합니다.

재귀를 이용하거나, 비트 연산을 이용하면 멱집합을 구할 수 있습니다.

​

1. 재귀를 이용하는 경우

현재 원소를 뽑거나 뽑지않는 경우로 나누어 재귀적으로 수행합니다.

​

2. 반복문을 이용하는 경우

멱집합은 2^n개의 부분집합으로 이루어지므로 1을 n만큼 left shift한 갯수(1<<n)만큼 구해줘야합니다.

먼저 예를 들어, 초기 집합 A의 SIZE는 3이라고 가정하겠습니다.

그리고 SIZE만큼 비트 수를 가지는 집합이 있다고 할 때, 3비트 크기의 집합은,

{000, 001, 010, 011, 100, 101, 110, 111}이 있습니다.

여기에서 각 비트의 1과 0은 멱집합의 원소에 포함되었는지 여부를 의미합니다.

비트 010으로 보면, A[0], A[2]은 포함되어있지 않고, A[1]는 포함되어있습니다.

이러한 비트 형태로 멱집합을 구할 수 있습니다.

아래 소스코드에서 iteration 함수의 i를, 위의3비트 크기의 집합이라고 보겠습니다.

j는 A의 원소의 크기만큼 반복해줍니다.

1 << j를 하면, shift된 비트는 0으로 채워지게 되고, 그것을 i와 AND연산하면,

그 값이 1이상인지 확인함으로써 i의 j번째 비트가 1로 켜져있는지 확인할 수 있습니다.

이러한 과정을 통해 3비트 크기의 집합 속에서 각 부분집합의 원소들을 구해내고, 멱집합을 얻을 수 있습니다.

 

#include <stdio.h>
#include <string.h>
#define SIZE 5
int arr[5] = { 1,2,3,4,5 };
int temp[5];

void iteration() {
	// 멱집합은 2^n개의 부분집합으로 이루어지므로 1 << n 개만큼을 구해야함
	for (int i = 0; i < (1 << SIZE); i++) {
		for (int j = 0; j < SIZE; j++) {
			if ((i & (1 << j)) >= 1) {
				// 1을 j만큼 << shift하면, 그 공간은 0으로 채워짐.
				// 따라서, 각 멱집합에 해당하는 비트 형태의 i와 1 << j를 AND 연산했을 때,
				// 해당 원소가 켜져있으면(1), 그 값은 >= 1이 되고,
				// 현재 검사하고 있는 멱집합의 원소로 포함되는 것
				printf("%d ", arr[j]);
			}
		}
		printf("\n");
	}
	printf("\n\n");
}

void recursion(int idx, int c) {
	// 현재 원소를 뽑거나, 뽑지 않는 경우를 재귀적으로 수행함
	if (c == SIZE) {
		for (int i = 0; i < idx; i++) {
			printf("%d ", temp[i]);
		}
		printf("\n");
		return;
	}
	recursion(idx, c + 1); // 현재 원소를 뽑지 않음
	temp[idx] = arr[c];
	recursion(idx + 1, c + 1); // 현재 원소를 뽑음
}

int main() {
	printf("반복문 버전 : \n");
	iteration();
	printf("\n\n재귀 버전 : \n");
	recursion(0, 0);
}

 

// 실행 결과
반복문 버전 :

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




재귀 버전 :

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