부분집합(power set) 구하기(2)

앞에서 부분 집합 구하는 방법에 대해서 설명했습니다.
좀 더 쉽고 효율적인 방법에 대해서 알아보도록 하겠습니다.
http://swlock.blogspot.com/2016/03/power-set.html

위 방법의 문제점이 있습니다.

동전 거스름돈 문제처럼 동전이 여러개가 있는 문제를 해결하는데 어려움이 있습니다. 즉 위의 숫자 1,2,3이 동전이라고 가정할때 1,1,1,1, 2,2,2,2... 3,3,3,3,3... 동전이 여러개가 있다면 위의 방법으로는 구현이 어려움이 있습니다. 아래에 해당 문제가 있습니다.

http://swlock.blogspot.com/2016/05/blog-post.html

그림만 보면 어떻게 하라는 건지 이해하기가 난해합니다.
depth 1 에서 보면 처음에는 1을 선택하고 두번째는 2 세번째는 3을 선택합니다.
그리고 depth 2에서는 1을 선택했다면 두번째 인자를 선택하고 세번째 인자를 선택합니다.
다음 depth 3 에서는 마지막 3만 선택합니다. 최종 말단노드가 최종 값이 됩니다.

즉 재귀함수는 아래와 같이 구현이 될 겁니다.
powerset()
{
  for(i=0;i<N;i++){
    flag[i]=1;
    powerset();
    flag[i]=0;
  }
}
앗 위와같이하면 문제가 생깁니다. 즉 무한루프에 빠지게 됩니다. 왜냐하면 i가 항상 0부터 시작하므로 depth 2에서도 depth 1처럼 선택을하게 됩니다. 따라서 두번째 depth 에서 시작할 i는 이전에 전달이 되어야 합니다.
powerset(int starti)
{
  for(i=starti;i<N;i++){
    flag[i]=1;
    powerset(i+1);
    flag[i]=0;
  }
}
즉 현재 선택된 다음 부터 loop가 돌아야 합니다.
또한 마지막에 선택에 0이 선택되어서 돌아야 하므로 해당 코드가 더 추가 되어야 합니다.

powerset(int starti)
{
  for(i=starti;i<N;i++){
    flag[i]=1;
    powerset(i+1);
    flag[i]=0;
  }
  powerset(i+1);
}

아래 소스에서 powerset함수로 구현해 보았습니다.

이 방법보다는 좀 더 쉬운 방법도 있습니다.

선택된 항목을 미리 준비한 selected 배열에 넣는 방법입니다.

powerset2함수로 구현하였습니다.

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