멱집합(Power Set)

A의 모든 부분집합을 원소로 하는 집합을 A의 멱집합(power set)이라 하고 P(A) 또는 2^A로 나타낸다.

예를들어 S = { 1 , 2, 3, 4 } 일때 부분집합(power set) = {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}} 이다.

따라서 임의의 유한집합에 대해서 그 크기가 |A| = n 이라고 할때, 부분집합의 개수는 2ⁿ 개가 된다.  

 

그럼 컴퓨터에서 임의의 집합의 모든 부분집합을 출력하는 알고리즘은 어떻게 될까?

 

사실 생각해보면 { a, b, c, d, e, f } 의 모든 부분집합을 나열하려면 a 를 제외한 { b, c, d, e, f } 의 모든 부분집합들을 나열하고

{ b, c, d, e, f }의 모든부분집합에 { a } 를 추가한 집합들을 나열하면 되는 것돠 동일하다.

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

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

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

 

이 설명이 내포하고 있는 것은  재귀(recursion)이다.

즉, S의 멱집합을 출력하라는 문제는 재귀로 풀수 있다. 

물론 재귀 말고도 멱집합을 구하는 알고리즘은 더 있는데 여기서는 그 모든 방법을 다 알아보도록 한다. 

 

멱집합 알고리즘 - Recusrion

재귀함수는 반드시 빠져나갈 베이스케이스가 있어야 한다고 하였는데 여기서 베이스 케이스는 S가 비어 있는 경우 ( Φ (공집합) )이다.

 

 

 

public static ArrayList < String > getpowerset(int a[], int n, ArrayList < String > ps) {
    if (n < 0) {
        return null;
    }
    if (n == 0) {
        if (ps == null) ps = new ArrayList < String > ();
        ps.add(" ");
        return ps;
    }
    ps = getpowerset(a, n - 1, ps);
    ArrayList < String > tmp = new ArrayList < String > ();
    for (String s: ps) {
        if (s.equals(" ")) tmp.add("" + a[n - 1]);
        else tmp.add(s + a[n - 1]);
    }
    ps.addAll(tmp);
    return ps;
}

 

 

멱집합 알고리즘 - Iterative

 

public static <T> List<List<T>> powerset(Collection<T> list) {
  List<List<T>> ps = new ArrayList<List<T>>();
  ps.add(new ArrayList<T>());   // add the empty set
 
  // for every item in the original list
  for (T item : list) {
    List<List<T>> newPs = new ArrayList<List<T>>();
 
    for (List<T> subset : ps) {
      // copy all of the current powerset's subsets
      newPs.add(subset);
 
      // plus the subsets appended with the current item
      List<T> newSubset = new ArrayList<T>(subset);
      newSubset.add(item);
      newPs.add(newSubset);
    }
 
    // powerset is now powerset of list.subList(0, list.indexOf(item)+1)
    ps = newPs;
  }
  return ps;
}
 

 

멱집합 알고리즘 - Binary String

public static < T extends Comparable < ?super T >> LinkedList < LinkedList < T >> BinPowSet(
LinkedList < T > A) {
    LinkedList < LinkedList < T >> ans = new LinkedList < LinkedList < T >> ();
    int ansSize = (int) Math.pow(2, A.size());
    for (int i = 0; i < ansSize; ++i) {
        String bin = Integer.toBinaryString(i); //convert to binary
        while (bin.length() < A.size()) bin = "0" + bin; //pad with 0's
        LinkedList < T > thisComb = new LinkedList < T > (); //place to put one combination
        for (int j = 0; j < A.size(); ++j) {
            if (bin.charAt(j) == '1') thisComb.add(A.get(j));
        }
        Collections.sort(thisComb); //sort it for easy checking
        ans.add(thisComb); //put this set in the answer list
    }
    return ans;
}

 

 

 

 

 

 

 

 

레퍼런스

• https://rosettacode.org/wiki/Power_set