[알고리즘] 2-1. 멱집합

멱집합 (Powerset)

n개의 원소를 갖는 집합은 2^n개의 부분집합을 갖는다.

-> 부분집합에 원소를 추가한 집합들을 나열 [합집합 이용]

 

즉, S의 멱집합을 구한 후 각각에 집합 P를 합집합해 출력

-> 순환 함수가 두 개의 집합을 매개변수로 받도록 설계 후, 두 번째 집합의 모든 부분집합에 첫 번째 집합을 합집합해 출력

 

집합 S : k번째부터 n-1번째 원소를 가지는 집합

집합 P : 0번째부터 k-1번째 원소를 가지는 집합

 

//1. 멱집합 (Powerset)

//상태공간트리 이용

private static char data[] = {'a','b','c','d','e','f'};
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.println(data[i]+ " ");
  System.out.println();
  return;
 }
 include [k] = false;
 powerSet(k+1);
 //먼저 왼쪽으로 내려가고,
 
 include [k] = true;
 powerSet(k+1);
 //오른쪽으로 내려간다.
}