[Algorithm] stack을 이용한 순열(모든 부분집합, power set) 구하기

Stack을 이용한 순열 구하는 방법으로
아래와 같이 사용할 수 있다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <stdio.h>     // 배열 출력하기 void printSet(int array[], int size){         for (int i = 1; i <= size; i++)         printf("%d ", array[i]);     printf("\n");       return; }   // 반복문과 스택을 이용한 순열 구하기 void printPowerset(int n){     int stack[10], k;       stack[0] = 0; // 0은 제외     k = 0;       while (1){         if (stack[k]<n){             stack[k + 1] = stack[k] + 1;             k++;         }           else{             stack[k - 1]++;             k--;         }           if (k == 0)             break;           printSet(stack, k);     }       return; }   // 재귀를 통한 순열 구하기 void powersetRec(int s[], int k, int m, int n) {     if (m <= n) {         s[k + 1] = m;         printSet(s, k + 1);         powersetRec(s, k + 1, m + 1, n); /* with m */         powersetRec(s, k, m + 1, n); /*  without m */     } }   int main(){       int s[6]; // stack     powersetRec(s, 0, 1, 4);          printPowerset(4);       return 0; }   Colored by Color Scripter

cs

출력 결과물

1

1 2

1 2 3

1 2 3 4

1 2 4

1 3

1 3 4

1 4

2

2 3

2 3 4

2 4

3

3 4

4