[Java]부분 집합(Subset)과 멱집합(Power Set)

*부분 집합(Subset)

-> 부분 집합이란 쉽게 말해서 어떤 집합에 포함되는 집합을 말한다. 말 그대로 어떤 집합의 '부분'이 되는 집합이라고 생각하면 된다.

Ex) {1, 2, 3}의 부분 집합은 공집합, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이 있다.

 

*멱집합(Power set)

-> 멱집합이란, 해당 집합의 모든 부분 집합을 모아둔 것이다.

Ex) {1, 2, 3}의 멱집합은 {공집합, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} 이다.

 

*부분 집합 구하기

-> 부분 집합은 기본적으로 조합을 이용하여 쉽게 구할 수 있다. 어떤 집합에서 개수가 전체 원소의 개수가 n개인 부분 집합을 구한다면, 해당 집합에서 n개의 수를 '선택' 하면 된다. 부분 집합은 각 원소의 순서를 바꿔도 같은 부분집합이다. 따라서, 조합을 이용한다면 부분 집합을 쉽게 구할 수 있다.

 

*멱집합 구하기(조합 이용)

-> 멱집합은 해당 집합의 모든 부분 집합을 모은 것이라고 하였다. 따라서, 해당 집합의 원소의 개수가 총 N개라고 한다면 0부터 N개의 원소를 가지는 모든 부분 집합을 구하면 멱집합을 구할 수 있음을 알 수 있다. 따라서, 기본적으로 원소수를 바꿔 가면서 모든 조합을 구해주면 멱집합을 쉽게 구할 수 있다.

-> 예를 들어, 집합 {1, 2, 3}의 멱집합은 다음과 같이 구할 수 있다.

package cases;

import java.util.Arrays;

public class PowerSet_Combination {
	static int[] nums = { 1, 2, 3 };
	// 최대 원소의 개수
	static int max_cnt;
	// 각 부분 집합을 저장할 배열
	static int[] subset;

	public static void main(String[] args) {
		// 원소를 선택하는 개수 0 ~ 3개.
		for (int i = 0; i <= 3; i++) {
			max_cnt = i;
			subset = new int[i];
			// 대상 집합에서 원소를 0 ~ 3개를 선택하는 조합을 모두 구한다.
			Combination(0, 0);
		}
	}

	private static void Combination(int cnt, int k) {
		if (cnt == max_cnt) {
			System.out.println(Arrays.toString(subset));
			return;
		}
		for (int i = k; i < nums.length; i++) {
			subset[cnt] = nums[i];
			Combination(cnt + 1, i + 1);
		}

	}
}

 

*멱집합 원소의 개수(부분 집합의 총 개수)

-> 그렇다면 해당 집합의 모든 부분 집합의 개수, 즉 멱집합의 모든 원소의 개수는 몇 개 일까? 이 문제는 중복 순열의 개념을 응용하여 해결 할 수 있다. 

-> 예를 들어, 집합 {1, 2, 3}에서 부분 집합을 구하는 것은 3개의 공간에 각 숫자를 넣을 것인지 말 것인지를 결정하는 문제로 치환 가능하다. 즉, 1을 넣을 공간에 1을 넣을지 말지, 2를 넣을 공간에 2를 넣을지 말지, 3을 넣을 공간에 3을 넣을지 말지를 결정하여 부분 집합을 결정할 수 있다.

부분 집합을 구하는 것은 중복 순열 문제로 치환 가능하다!

-> 따라서 최종적으로 전체 원소의 개수만큼 해당 숫자를 선택할지/선택하지 않을지를 결정하면 되기 때문에, 부분 집합의 총 개수는 2의 N승(N은 대상 집합의 총 원소의 개수)이다.

 

*멱집합 구하기(재귀 이용)

-> 뜬금없이 부분 집합의 총 개수를 구하는 방법을 이야기한 이유는, 부분 집합의 총 개수를 구하는 로직을 이용하여 멱집합을 구하는 방법이 존재하기 때문이다. 해당 로직을 적절히 재귀로 구현하면 역시 멱집합을 구할 수 있다.

-> 보통 멱집합에서 재귀를 이용하는 로직을 설명하기 위해서 다음과 같은 설명을 자주 볼 수 있다. 예를 들어, 집합 {1, 2, 3}의 멱집합은 집합 {1, 2, 3}에서 원소 1을 제외한 부분 집합의 모든 멱집합의 원소에, 원소 1을 포함하여 생각해주면 된다. 즉, 집합 {2, 3}의 멱집합은 공집합, {2}, {3}, {2, 3}인데, 각 멱집합의 원소에 원소 1을 추가하여 생각해주면 {1}, {1, 2}, {1, 3}, {1, 2, 3}의 경우를 추가해줄 수 있다.  이러한 과정을 거치면 최종적으로 집합 {1, 2, 3}의 멱집합과 같아진다.

-> 위의 로직은 쉽게 말해 앞에서 언급한 부분 집합의 총 개수를 구하는 로직과 같다. 즉, 어떤 원소를 포함 시킬 것인지 아니면 포함시키지 않을 것인지를 고민하며 선택을 반복하면 최종적으로 모든 부분 집합을 구할 수 있다. 집합 {1, 2, 3}의 부분 집합을 어떤 원소를 포함 시키느냐, 포함 시키지 않느냐의 문제로 해결 하는 예로 아래 트리 구조를 참고하자.

어떤 문제를 선택하느냐, 선택하지 않느냐의 문제이기 때문에 포화 이진 트리의 구조를 갖는다

-> 즉, 이렇게 이진 트리의 구조를 가지고 있기 때문에 재귀를 이용한다면, 최종적으로 모든 멱집합의 개수를 구할 수 있다. 해당 숫자를 선택했는지, 선택하지 않았는지를 표현하기 위해서 visited boolean 배열을 만들어 활용할 수 있다.

package cases;

public class PowerSet_Recursion {
	static int[] nums = { 1, 2, 3 };
	// 해당 숫자를 선택 했는지, 선택하지 않았는지를 표현해줄 배열.
	static boolean[] visited = new boolean[3];

	public static void main(String[] args) {
		// 아무것도 선택하지 않는 경우부터 시작한다.
		powerSet(0);
	}

	private static void powerSet(int cnt) {
		// 3개의 숫자에 대한 선택을 완료 하였다면, 선택된 숫자들을 출력한다.
		// 선택된 각 숫자들은 대상 배열의 '부분 집합'이다!
		if (cnt == nums.length) {
			for (int i = 0; i < nums.length; i++) {
				// 숫자가 선택 되었다면 출력한다.
				if (visited[i]) {
					System.out.print(nums[i] + " ");
				}
			}
			System.out.println();
			return;
		}

		// 해당 숫자를 선택하고 재귀를 진행한다.
		visited[cnt] = true;
		powerSet(cnt + 1);
		// 해당 숫자를 선택하지 않고 재귀를 진행한다.
		visited[cnt] = false;
		powerSet(cnt + 1);
	}
}

.

※ 출력 결과를 보면 위의 트리와 출력 순서가 같은 것을 확인 할 수 있다.