[알고리즘][Recursion] 멱집합(Power Set)

1. 멱집합(Power Set)이란 무엇인가?

멱집합이란 주어진 집합의 모든 부분집합들로 구성된 집합을 의미합니다. 예를 들어 아래 집합 S에 대한 모든 부분집합은 다음과 같습니다. 요소의 개수 3개인 집합 S 모든 부분집합의 개수는 총 8개입니다. 이는 멱집합의 부분집합의 개수는 2ⁿ개임을 알 수 있습니다.

S = {a,b,c}
Power set = {ø, {c}, {b}, {b,c}, {a}, {a,c}, {a,b}, {a,b,c}}

 

 

위 집합 S={a,b,c}의 모든 부분집합을 나열하려면 다음과 같습니다.

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

 

다시 {b,c}의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면 다음과 같습니다.

• {c}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고 (a포함, b 미포함)
• {c}의 모든 부분집합들에 {a,b}를 추가한 집합들을 나열합니다. (a포함, b포함)

위의 자세한 과정을 상태 공간 트리(state space tree)로 표현하면 다음과 같습니다.

 

 

상태 공간 트리(state space tree)란 무엇인가?

• 해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리
• 트리의 모든 노드들을 방문하여 해를 찾을 수 있습니다.
• 루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술합니다.

 

2. 멱집합의 의사코드(pseudocode)

집합 S의 멱집합을 출력하기 위한 의사코드(pseudocode)로 표현하면 다음과 같습니다.

powerSet(S)
{
    if 집합 S가 비어있는 경우
    	아무것도 출력하지 않음;
    else
    	집합 S의 첫번째 요소를 변수 t에 저장;
        집합 S에서 t를 포함하지 않는 모든 부분집합들을 탐색;
        t를 포함하지 않는 부분집합 출력
        t를 포함하는 부분집합 출력
}

위의 의사코드를 Java 코드로 표현하면 아래와 같습니다.

public class PowerSetProblem {
	private static String data = "abc";
	
	public static void powerSet(String S)
	{
		if(S.length()==0)
		{
			return;
		}
		else
		{
			String t = String.valueOf(S.charAt(0));
			S = S.substring(1);
			powerSet(S);
			System.out.println(S);
			System.out.println(t+S);
		}
	}
	
	public static void main(String[] args)
	{
		powerSet(data);
	}
}

Output

c
c
bc
bc
abc

 

위 코드의 출력결과 우리가 예상한 결과가 나오지 않았습니다. 그 이유는 powerSet() 메서드를 재귀적으로 호출은 하였으나 return문이 아무것도 반환을 하지 않아서 집합 S에서 t를 포함하지 않는 모든 부분집합만을 출력하고 종료됩니다.

 

따라서 다음과 같이 의사코드를 개선합니다. 

powerSet(P, S)
{
    if S 집합이 비어있는 경우
    	집합 P의 원소들 출력
    else
    	변수 t에 S의 맨 앞의 요소를 저장한다
        집합 S에 t를 포함하지 않는 모든 부분집합을 나열 ( powerSet(P, S-{t}) )
        집합 S에 t를 포함하지 않는 모든 부분집합에 t를 추가한 모든 부분집합을 나열 ( powerSet(PU{t}, S-{t} )
}

위의 의사코드는 집합 S의 모든 부분집합을 구한 후 각각에 집합 P를 합집합(U)하여 출력합니다. 맨 처음 powerSet() 메서드 출력시 P는 공집합("")입니다.

 

실제 Java 기반 언어로 코드를 구현시 집합 P는 include라는 이름의 boolean 배열로 표현하고 집합 S는 문자열 data로 표현합니다. 대신 powerSet 메서드의 매개변수로 변수 k를 정의하여 변수 k와 include 배열을 이용하여 내 위치가 어디있는지  파악할 수 있습니다.

 

예를 들어 {b,c}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다면 다음과 같습니다.

• {c}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고 (a포함, b미포함)
• {c}의 모든 부분집합들에 {a,b}를 추가한 집합들을 나열합니다. (a포함, b포함)

위의 과정을 수행하면 {b,c}의 모든 부분집합에 {a}를 추가한 집합들은 {a}, {a,c}, {a,b}, {a,b,c}가 됩니다. 상태공간트리로 표현하면 아래 그림과 같습니다.

 

위 수행 과정에서 {c}의 모든 부분집합은 집합 S이고 k번째부터 마지막 원소(n-1)까지 연속된 원소들입니다. 그리고 {a}, {a,b}를 추가하는 집합들은 집합 P이고 0번째부터 k-1번째 원소들 중 일부(포함/미포함)입니다.

 

위의 설명을 그림으로 표현하면 다음과 같습니다. 아래의 상황은 k=2이고 {c}의 모든 부분집합들에 {a,b}를 추가한 집합들을 나열하는 과정중에 있습니다. 이때 include[2]=false이므로 c는 포함되지 않아서 {a,b}라는 하나의 부분집합이라는 결과가 출력됩니다. 즉, k=2일때 0~k-1의 범위는 이미 원소들(a,b)을 포함할지 말지 이미 결정된 상태이고 2번째 원소인 c는 분기점에 있는 것입니다. 만약 c가 포함되지 않으면 {a,b}가 모든 부분집합 중 하나가 되고 c가 포함된다면 {a,b,c}가 모든 부분집합중 하나가 됩니다.

 

위의 예제를 기반으로 개선된 powerSet 메서드를 구현하면 다음과 같습니다.

public class PowerSet {
	private static char data[] = {'a','b','c'};
	private static int n = data.length;
	private static boolean[] include = new boolean[n];

	public static void powerSet(int k)
	{
		if(k==n)
		{
			for(int i=0;i<n;i++)
			{
				if(include[i])
				{
					System.out.print(data[i] + " ");
				}
			}
			System.out.println();
			return;
		}
		include[k] = false; //k번째 원소를 제외
		powerSet(k+1);		//k+1이후의 부분집합의 멱집합 탐색
		include[k] = true;	//k번째 원소 포함
		powerSet(k+1);		//k+1이후의 부분집합의 멱집합 탐색
		
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		powerSet(0);
	}

}

 

Output

c 
b 
b c 
a 
a c 
a b 
a b c

 

정리

멱집합(powerSet)이란 집합에 존재하는 모든 원소를 대상으로, 모든 부분집합을 가지는 집합을 의미합니다. 멱집합을 재귀적으로 구하기 위해서는 하나의 원소가 포함되어 나머지 원소들의 부분집합들과 합하여 나열되는 경우와 하나의 원소가 포함되지 않고 나머지 원소들의 부분집합들이 나열된다면 모든 부분집합들을 나열 할 수 있습니다.

 

References

source code : https://github.com/yonghwankim-dev/inflearn_algorithm/tree/master/section02_Recursion_07
[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌