7. 멱집합(Powerset)

7. 멱집합(Powerset)

 

멱집합

임의의 집합의 모든 부분집합

​

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

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

​

집합 S

: k번째부터 마지막 원소까지 연석된 원소들

: data[k], ..., data[n-1]

집합P

: 처음부터 k-1번째 원소들 중 일부

: include[i] = true (i = 0, ..., k-1)

 

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.print(data[i] + "");
      System.out.println();
      return;
   }

   include[k] = false;
   powerset(k+1); //왼쪽으로 내려갔다가
   include[k] = true;
   powerSet(k+1); //오른쪽으로 내려간다.
}

 

상태공간 트리 (state space tree)

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

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

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