[알고리즘] 멱집합

임의의 집합 data의 모든 부분집합을 출력하라.

 

멱집합을 구하는 것에는 몇가지 알려져있는 방법이 있습니다. recursion을 이용해서 해결하는 방법은 가장 간명한 알고리즘 중 하나입니다. 

 

Powerset

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

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

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

 

powerSet(S)
IF S IS AN EMPTY SET
	print nothing;
else
	let t be the first element of s;
    find all subsets of S-{t} by calling powerSet(S-{t});
    print the subsets;
    print the subsets with adding t;

 

멱집합(Powerset) 구하기

멱집합(Powerset)이란 어떤 집합 SSS의 모든 부분집합을 의미합니다. 이를 구하는 과정에서 집합 PPP를 활용하여 각 부분집합에 특정 원소를 포함하거나 포함하지 않는 방식으로 탐색합니다.

---

1. 개념 정리

1. 입력: 두 개의 집합 SSS와 PPP
   • SSS : 멱집합을 구할 대상이 되는 집합
   • PPP : 현재까지 선택된 원소들의 집합 (초기에는 공집합)
2. 출력: S의 모든 부분집합을 구한 후, 각 부분집합에 P를 합집합하여 출력
3. 재귀(recursion) 과정:
   • 현재 원소를 포함하는 경우와 포함하지 않는 경우로 나누어 탐색
   • 탐색을 위해 불리언 배열 include를 사용
     • include[k] = True → k번째 원소를 포함
     • include[k] = False → k번째 원소를 제외
   • SSS의 모든 부분집합을 생성한 후, include 배열에서 True인 원소들만 선택하여 출력

---

2. 재귀적 접근 방식

• 기본 사례(Base Case):
  • 집합 S가 공집합이면 현재까지 포함된 원소들(즉, include에서 True인 원소들)을 출력
• 재귀 단계(Recursive Case):
  • k번째 원소를 포함하지 않는 경우
  • k번째 원소를 포함하는 경우
  • 각 단계에서 부분집합을 재귀적으로 탐색

---

3. 알고리즘 동작 방식

1. SSS의 원소 개수가 n일 때, include 배열을 크기 n으로 생성
2. 초기 호출 시 powerset(0)을 수행하여 전체 탐색 시작
3. 현재 k번째 원소를 포함할지 여부를 결정
4. 모든 부분집합이 탐색되면 include가 True인 원소들을 출력

상태 공간 트리

-해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리

-트리의 모든 노드들을 방문하면 해를 찾을 수 있음

-루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술

 

해를 찾는다는 것은 상태공간트리의 모든 것을 가보면 문제에 대한 해를 찾게 됩니다.

 

private static char data[] = { 'a','b','c','d','e' };
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.printIn();
		return;
	}
	include[k] = false;
	powerSet(k + 1);
	include[k] = true;
	powerSet(k + 1);
}