[알고리즘] 재귀: 멱집합(Powerset), 순열 구하기

멱집합(Powerset)

data = {a, b, c, d} 가 존재할 때
이 집합의 멱집합은 ∅, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d} ...

어떤 집합이 존재할 때 그 집합의 모든 부분집합의 집합을 멱집합(Powerset)이라고 한다.

{a, b, c, d} 의 모든 부분집합을 나열하기 위해서는

1. a 를 제외한 {b, c, d} 의 모든 부분집합을 나열하고
2. {b, c, d} 의 모든 부분집합에 a 를 추가한 집합들을 나열한다.

이후 {b, c, d} 의 모든 부분집합을 나열하기 위해 위와 같은 과정을 반복하고, {c, d} 의 모든 부분집합을 나열하기 위해 또 반복하며 모든 부분집합을 구할 때까지 순환하며 멱집합을 구한다.

소스코드

char data[4] = { 'a','b','c','d' };
int N = 4;
bool include[17];
void powerSet(int k) {
	if (k == N) {
		for (int i = 0; i < N; i++) {
			if (include[i])
				printf("%c ", data[i]);
		}
		printf("\n");
		return;
	}
	include[k] = false;
	powerSet(k + 1);
	include[k] = true;
	powerSet(k + 1);
}

함수 호출 시에 powerSet(0) 와 같이 k = 0부터 시작하여 배열 사이즈 N이 k와 같아질때까지 순환한다. 만약 N == k라면 include 표시한 데이터들을 출력하고 리턴한다.

출력결과

이때 맨 위의 공백은 공집합을 나타낸다.

---

순열

data = {a, b, c, d} 가 존재할 때
이 집합의 모든 가능한 순열은 {a, b, c, d}, {a, b, d, c}, {a, c, b, d}, {a, c, d, b} ...

집합의 모든 순열을 구하는 방법은 멱집합을 구하는 과정과 비슷하다.

{a, b, c, d} 의 모든 순열을 구하기 위해서는

1. 첫 원소가 a 이면서 {b, c, d} 의 모든 순열을 더한 것과
2. 첫 원소가 b 이면서 {a, c, d} 의 모든 순열을 더한 것
3. 첫 원소가 c 이면서 {a, b, d} 의 모든 순열을 더한 것
4. 첫 원소가 d 이면서 {a, b, c} 의 모든 순열을 더한 것

을 순환을 통해 찾는다.

소스코드

char data[4] = { 'a','b','c','d' };
int N = 4;
void perm(int k) {
	if (k == N) {
		for (int i = 0; i < N; i++)
			printf("%c ", data[i]);
		printf("\n");
		return;
	}
	for (int i = k; i < N; i++) {
		swap(data, k, i);
		perm(k + 1);
		swap(data, k, i);
	}
}

출력결과

참고자료
멱집합 (powerset) / https://youtu.be/nkeMRRIVW9s
순열 (permutation) / https://youtu.be/MjW10t9ppok