부분 집합 구하기

이 글에서는 부분 집합을 구하는 2가지 방법에 대해 설명할 것입니다.

0. 부분 집합이란?

두 집합 A = {1, 2, 3}, B = {1, 2, 3, 4, 5} 에서 집합 A의 원소(1, 2, 3)는 집합 B의 원소임을 알 수 있습니다.
이와 같이
x∈A -> x∈B 명제가 성립하면 A를 B의 부분 집합이라 부르고, A⊂B 또는 B⊃A 로 나타내며 A는 B에 포함된다 또는 A는 B의 부분 집합이다 라고 말하니다.

{1, 2, 3}의 부분 집합을 구하면,
{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 총 8가지입니다.
지금부터는 이런 부분 집합을 어떻게 구하는지 알아볼 것입니다.

1. 재귀 호출

{1, 2, 3}의 부분 집합을 구하는 과정을 트리 로 나타내면,

이 과정을 통해 구할 수 있고, 이것을 재귀로 짜면 다음과 같습니다.

void subset(n, depth){ //n:전체 집합 원소 개수   depth:현재 트리 깊이
    flag[depth] = 0;
    subset(n, depth+1);
    flag[depth] = 1;
    subset(n, depth+1);
}

그리고, 재귀 함수는 탈출 조건이 있어야 합니다.
현재 깊이와 전체 원소의 개수가 같으면 트리의 마지막까지 도달한 것이니까 탈출을 하면 됩니다.
위 코드에 탈출 조건을 더한 것을 다음과 같습니다.

void subset(n, depth){ //n:전체 집합 원소 개수   depth:현재 트리 깊이
    if(n == depth){
        print result;
        return;
    }
    flag[depth] = 0;
    subset(n, depth+1);
    flag[depth] = 1;
    subset(n, depth+1);
}

전체 코드를 봅시다.

#include <stdio.h>

int set[] = {1, 2, 3};
int flag[] = {0, 0, 0};

void subset(int n, int depth){
	if(n == depth){
		int i;
		printf("{");
		for(i=0; i<n; i++){
			if(flag[i]) printf("%d ", set[i]);
		}
		printf("}\n");
		return;
	}
	flag[depth] = 0;
	subset(n, depth+1);
	flag[depth] = 1;
	subset(n, depth+1);
}

int main(){
	subset(sizeof(set)/sizeof(int), 0);
}

비트 마스크

위에 있는 트리 사진을 보면 flag가 binary 형태인 것을 알 수 있습니다. (000, 001, 010, 011 …)
그래서 이 것을 이용해 재귀호출을 쓰지 않고, 반복문만 써서도 부분 집합을 구할 수 있습니다.
001 이면 3번째 원소만, 101이면 1번째와 3번째 원소를 출력하는 방식으로 하면 간단히 구현할 수 있습니다.

#include <stdio.h>

int set[] = {1, 2, 3};

void subset(int n){
	int pow = 1<<n;
	int i, j;
	for(i=0; i<pow; i++){
		printf("{");
		for(j=0; j<n; j++){
			if(i & (1<<j)) printf("%d ", set[j]);
		}
		printf("}\n");
	}
}

int main(){
	subset(sizeof(set)/sizeof(int));
}

목차

0. 부분 집합이란?

1. 재귀 호출

비트 마스크