부분집합(power set) 구하기

부분집합 : 집합에 포함된 원소를 선택하는 것

예) {1,2,3} 의 부분 집합
{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}
=> 공집합 + 1개의 원소를 가지는 집합 + 2개의 원소를 가지는 집합 + 3개의 원소를 가지는 집합 => 각각은 조합 원소의 값과 같음 (3C0+3C1+3C2+3C3)

1,2,3의 부분 집합 선택하는 과정을 그림으로 표시하면 아래와 같습니다.

위에서 각 node에 대해 2개씩 선택됩니다.
따라서 재귀적으로 2번씩 선택하면 쉽게 구현이 가능하리라 생각되네요.
이것을 재귀 수도 코드 형태로 나태내면 아래와 같습니다.

powserset(n,depth)
{
    flag[depth]=1;
    powserset(n,depth+1)
    flag[depth]=0;
    powserset(n,depth+1)
}

여기에서 탈출 조건을 생각해 봅시다.
탈출조건이란 재귀 함수에서 재귀를 마치고 리턴되는 조건을 의미하는데 depth와 인자 갯수 n이 되면 출력을 해야합니다.
아래와 같이 생각해 볼 수 있습니다.

powserset(n,depth)
{
    if( n==depth){
        print
        return
    }
    flag[depth]=1;
    powserset(n,depth+1)
    flag[depth]=0;
    powserset(n,depth+1)
}

이것을 코드로 구현해 보았습니다.

C, pasted 1 second ago:  #include <stdio.h> int data[]={1,2,3,4}; int flag[]={0,0,0,0}; void powerset(int n,int depth) { if(n==depth){ int i; printf("{"); for(i=0;i<n;i++){ if(flag[i]==1)printf("%d ",data[i]); } printf("}\n"); return; } flag[depth]=1; powerset(n,depth+1); flag[depth]=0; powerset(n,depth+1); } int main() { powerset(sizeof(data)/sizeof(int),0); return 0; } Output: {1 2 3 4 } {1 2 3 } {1 2 4 } {1 2 } {1 3 4 } {1 3 } {1 4 } {1 } {2 3 4 } {2 3 } {2 4 } {2 } {3 4 } {3 } {4 } {}

powerset은 다른 형태로 구현을 할 수 있습니다.
위 그림에서 flag값 형태를 보면
111, 110, 101 ... binary가 세는 형태(감소 또는 증가)로 생각해볼 수 있습니다. 그래서 아래와 같은 방법으로도 구현할 수 있습니다. 참고로 이러한 형태가 되면 32bit 나 64bit등 system에서 제공되는 data의 bit수 최대 크기로만 지원이 가능하다는 제약 조건이 있습니다.

C, pasted just now: 

#include <stdio.h> int data[]={1,2,3,4}; void powerset(int n) { int i,j; int max = 1<<n; for(i=0;i<max;i++){ printf("{"); for(j=0;j<n;j++){ if(i & (1<<j)) printf("%d ",data[j]); } printf("}\n"); } } int main() { powerset(sizeof(data)/sizeof(int)); return 0; }

Output:

{} {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 }

또 다른 방법으로는 DP를 이용할 수 있다.
http://swlock.blogspot.com/2016/03/dp-power-set-with-dp.html

또 다른 방법
http://swlock.blogspot.com/2016/06/power-set-2.html