[Algorithm] 2-7. Recursion 응용 4 - 멱집합, PowerSet

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크

2-7. Recursion의 응용 4 - 멱집합

멱집합 - Powerset

• 어떤 집합의 모든 부분집합을 멱집합이라고 부른다.

• 임의의 집합 data = {a, b, c, d}의 모든 부분집합은

  • 2ⁿ = 16개 이다.

Recursion을 이용하여 모든 부분집합을 나열

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

  • 먼저 a를 포함하지 않는 부분집합과

  • a를 포함하는 부분집합으로 나눌 수 있다.

  • 따라서, 아래와 같이 표현할 수 있다.

    • a를 포함하지 않는 부분집합

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

    • a를 포함하는 부분집합

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

  • 위의 두가지를 합치면 경우의 수가 2ⁿ개가 되는 것이다.

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

  • 다시 한번 b를 포함하지 않는 부분집합과

  • b를 포함하는 부분집합으로 나누어 생각한다.

  • 따라서,

    • b를 포함하지 않는 부분집합

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

    • b를 포함하는 부분집합

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

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

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

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

Recursion으로 표현

• S의 멱집합을 출력하라

  • 아래와 같이 S에서 t를 뺀 집합의 모든 부분집합을 구하고 return을 하면,

  • 모든 부분집합을 저장해야하기 때문에, 모든 부분집합을 출력하는 문제를 해결하는데에는 적합하지 않을 수 있다.

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});
    return all of them;

• 따라서, 아래와 같이 변경을 한다.

  • else문에서 보면 S에서 t를 뺀 집합의 모든 부분집합을 구하고 print해주는 부분이 있다.

  • 하지만, 이렇게 변경을 해도 모든 부분집합에 t를 추가한 집합들을 나타내는 subsets with adding t를 해결할 수 없다. 코드에서 모든 부분집합을 저장하지 않았기 때문에.

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;

resursion의 설계 자체를 수정해야 할 필요가 있다.

• 위의 recursion 구현에서 결과적으로 모든 부분집합에 t를 추가한 집합들을 나타내는 작업을 수행하는데서 문제가 있었다. 아래의 단계이다.

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

  • b를 포함하지 않는 부분집합

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

  • b를 포함하는 부분집합

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

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

  • 어떤 집합의 모든 부분집합을 구해서, 그 결과에 또 다른 집합을 추가해서 출력하는 일을 할 수 있도록 설계가 바뀌어야 한다.

• Mission : S의 멱집합을 구한 후 각각에 집합 P를 합집합하여 출력하라

  • S : {c, d, e, f} - k번째 부터 마지막 원소까지 연속된 원소들이다.

  • P : {a, b} - 처음부터 k-1번째 원소들 중 일부이다.

  • recursion 함수가 두 개의 집합을 매개변수로 받도록 설계해야 한다는 의미이다. 두 번째 집합의 모든 부분집합들에 첫번째 집합을 합집합하여 출력한다.

  • 맨 처음 초기 호출은 powerSet(null, S)으로 하면 된다. S의 멱집합을 구하기 위한 호출이다.

  
  powerSet(P, S)
    if S is an empty set
      print P;
    else
      let t be the first element of S;
      powerSet(P, S-{t});
      powerSet(P 합집합 {t}, S-{t});

• S와 P를

  • S : k번째 부터 마지막 원소까지 연속된 원소들이다.

  • P : 처음부터 k-1번째 원소들 중 일부이다.

  • 아래와 같이 S와 P를 k라는 인덱스와 P라는 boolean 배열을 이용해서 나타낸다.

Powerset Java 구현

Mission : data[k], … , data[n-1]의 멱집합을 구한 후 각각에 include[i]=true, i=0,…,k-1, 인 원소를 추가하여 출력하라.

• 처음 함수 호출은 powerSet(0)으로 호출한다. 즉, P는 공집합 S는 전체집합.

• data[] 배열 중에서 인덱스 k부터 마지막까지 집합 S이고,

• data[] 배열 중에서 인덱스 0부터 k-1까지의 집합중 true인 값을 가지고 있는 것 들이 집합 P이다. 그리고 이것은 include로 표현한다.

• Base case는 집합 S가 공집합일 경우이다. 그 경우에는 그냥 P를 출력하면 된다. data중에 include에서 유지하고 있는 값이 true인 요소들.

• 일반적인 경우에는

  • data[k]를 포함하지 않는 경우

    • data[k]가 'a'라고 할 때, include[k]를 false로 놓고 powerSet의 매개변수를 'b'부터 끝원소까지의 집합으로 재귀호출한다.

    
    include[k] = false;
    powerSet(k + 1);

  • data[k]를 포함하는 경우

    • data[k]가 'a'라고 할 때, include[k]를 true로 놓고 powerSet의 매개변수를 'b'부터 끝원소까지의 집합으로 재귀호출한다.

    
    include[k] = true;
    powerSet(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)

• 원소가 {a, b, c}일 때, 구할 수 있는 모든 부분집합을 나타내는 트리이다.

• include와 exclude가 반대로 표기되어있다.

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

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

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

• 즉, 위의 코드를 상태공간트리의 관점에서 보면

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);
}

• 상태공간트리의는 이런 방식의 Recursion을 이해하는데 도움을 주는 매우 강력한 도구이며, 앞으로 더 알아갈 것이다.