Java - powerset(멱집합)

1. 문제

• 집합을 입력받아서 그 집합의 멱집합을 구하라.
• 멱집합(Powerset)이란?
  ▶ 주어진 집합의 모든 부분 집합들로 구성된 집합

---

2. 생각(Recursion Thinking) 

고등학교때 배운 내용을 떠올리며, set A = {a, b, c, d, e, f}가 존재한다고 가정한다.

 

Q) 집합 A의 부분 집합의 갯수는 몇 개인가?

집합의 원소들은 "부분 집합내에 존재하는가?"에 따라서 두 가지 경우의 수를 갖는다. 이를 바탕으로 모든 원소가 존재하지는 공집합 부터 모든 원소가 존재하는 경우까지 경우의 수를 생각하면 집합 A의 부분 집합의 갯수는 2^6 = 32개이다.

 

2.1. Powerset를 구현하는 알고리즘 아이디어

부분 집합의 갯수를 세는 것처럼 "특정 원소가 부분 집합에 존재하는가?"를 이용하여 특정 원소가 존재하는 경우와 존재하지 않는 경우로 나누어서 멱집합(powerset)를 구할 수 있다.

Powerset algorithm

 

◎ {a, b, c, d, e, f}의 모든 부분 집합을 나열하려면

• 원소 a가 존재하는 경우)  a를 제외한 {b, c, d, e, f}의 모든 부분 집합들을 나열하고,
• 원소 a가 존재하지 않는 경우)  {b, c, d, e, f}의 모든 부분 집합에 {a}를 추가한 집합들을 나열한다.

원소 a를 추가하는 경우에서 한 단계 더 들어간다면

 

◎ {b, c, d, e, f}의 모든 부분 집에 {a}를 추가한 집합들을 나열하려면

• 원소 b가 존재하지 않는 경우) {c, d, e, f}의 모든 부분 집들에 {a}를 추가한 집합들을 나열하고,
• 원소 b가 존재하는 경우) {c, d, e, f}의 모든 부분 집들에 {a, b}를 추가한 집합들을 나열한다.

 

위 알고리즘 아이디어를 정리하면

"어떤 집합(A)의 부분 집합을 구하기 위해서는 원소 하나(a)를 제거한 다른 집합(B, 집합 A의 부분 집합)의 부분 집합을 구한 뒤, 원소 하나(a)를 추가하거나 그대로 출력하면 어떤 집합(A)의 부분 집합을 구할 수 있다."

 

2.2. Recursion 구현

Recursion으로 구현함에 있어 필요한 정보는 두 가지 정보로 나눌 수 있다.

• State-space tree내에서 현재 어떤 노드에 있는가?
• 이전 노드에서 어떤 원소들이 선택되었는지?

위 정보들을 토대로 어떤 원소를 선택할 것인지를 결정하고, 다음 레벨(노드)로 진행하는 것이다. 두 가지 정보를 파라미터로 전달하는 방법에는 여러 가지가 존재하지만, 최대한 적은 갯수의 파라미터를 통해 정보를 전달하고자 한다.

 

2.3. Parameter of Recursion

원소의 갯수와 동일한 boolean 배열을 생성한다. 이 배열은 집합 A의 원소들이 선택 받았는지를 알려준다.  

배열 A = {a, b, c, d}의 부분 집합 중에서 {b, d}를 선택하는 경우

 위 경우 처럼 배열 A의 원소들이 포함 되었는지 여부를 include 배열이 갖고 있으며, 탐색 레벨이 배열 A이 도달하게 되면 include 배열의 true or false를 바탕으로 원소들을 출력하게 되면 배열 A의 부분 집합 중 하나인 {b, d}를 출력할 수 있다. 

 

즉, 특정 원소가 포함되었는지 여부를 include 배열에 저장하고, state-space tree에서 탐색 레벨이 배열A의 끝에 도달하게 되면 include 배열을 토대로 원소들을 출력함으로써 배열 A의 멱집할을 출력할 수 있는 것이다.

---

3. 풀이 및 코드 분석

import java.util.Scanner;

public class PowerSet {
	private static String[] list;
	private static boolean[] include;
	private static int size;
	public static void main(String[] args) {
		getArrayElement();
		int size = powerSet(0);
		System.out.printf("The number of poewrset is %d.\n", size);
	}
	
	/// *** Get element of array.
	private static void getArrayElement() {
		Scanner scan = new Scanner(System.in);
		
		while(true) {
			System.out.print("Enter size of array: ");
			size = scan.nextInt();
			
			if(size<=0)
				System.out.println("The size is less than or equal to 0.");
			else
				break;
		}
		
		list = new String[size];
		include = new boolean[size];
		
		System.out.print("Enter: ");
		for(int i=0; i<size; i++)
			list[i] = scan.next();
	}

	
	private static int powerSet(int k) {
		// ** Base case : 탐색 레벨이 배열 끝에 도달
		if(k==size) {
			System.out.print("Powerset = { ");
			for(int i=0; i<size; i++) {
				if(include[i]) {
					System.out.print(list[i] + " ");
				}
			}
			System.out.println("}");
			return 1;
		}else {
			// ** Recursion case
			int size = 0;
			// ** 원소를 포함하지 않는 경우
			include[k] = false;
			size += powerSet(k+1);
			// ** 원소를 포함하는 경우
			include[k] = true;
			size += powerSet(k+1);
			return size;
		}
	}

---

4. 메모