주어진 집합의 모든 부분집합을 구하기

   문제는, 말 그대로 간단하다. 주어진 배열의 모든 부분집합을 구해내는 것. 짱구 한 10분 굴려 나온 코드의 아이디어를 스케치 해보자.

   우리가 일반적으로 주어진 배열에 대하여 k-개의 원소로 된 부분집합을 다 구하고자 할 때는 다음과 같은 절차를 따르게 된다.

위에서 붉은 색이 선택한 요소라 하자. 위 그림은 2개의 원소로 된 부분집합을 모두 구하는 절차를 표현한 것이다. 우선 가장 왼쪽의 요소 2개를 선택할 것이다. 그 후, 가장 오른쪽 요소를 한 칸 오른쪽으로 옮기겠지. 이런 식으로 계속 오른쪽으로 한 칸씩 옮기면서 2개로 된 부분집합을 만들어 나가는 것이다. 그러다 더이상 움직일 수 없다면 이제 바로 앞의 요소를 한 칸 오른쪽으로 옮기는 것이다. 물론 이 단계에서 가장 오른쪽에 있던 요소는 다시 앞으로 이동을 하되, 현재 오른쪽으로 옮긴 요소보다는 바로 앞 칸에 있어야 하겠지(위 그림에서 (1) 이라고 표시된 부분).

   위 절차를 일반성을 잃지 않고 (ㅋㅋ without loss of generality^[각주:1]), 자연수 k 개로 확장하면^[각주:2] 우리가 원하는 알고리즘이 된다. 코드로 표현하면 다음과 같다.

#! /usr/bin/python
#-----------------------------------------------------------------------------#
def copy(src_list, index_list):
        result = [];
        for i in index_list:
                result.append(src_list[i]);

        return result;
#-----------------------------------------------------------------------------#
def forward_index(idx, max_length):
        changed = False;
        r = range(0,len(idx));
        r.reverse();
        idx_length = len(idx);
        for i in r:
                if idx[i] == max_length - idx_length + i:
                        continue;
                else:
                        # 이 부분이 위 그림에서 (1) 이라고 표현된 부분
                        idx[i] = idx[i] + 1;
                        for j in range(i+1, idx_length):
                                idx[j] = idx[j-1]+1;
                        changed = True;
                        break;

        if changed == True: return idx;
        else:
                return [];
#-----------------------------------------------------------------------------#
def ksubset(L, k):
        src_length = len(L);
        if src_length < k: return [];
        if src_length == k: return [L];
        if src_length == 0: return [];  

        max_length = src_length;
        ksubsets = [];
        idx = range(0,k);
        while idx != []:
                subset = copy(L, idx);
                ksubsets.append(subset);
                idx = forward_index(idx, max_length);
        
        return ksubsets;
#-----------------------------------------------------------------------------#
def allsubsets(L):
        result = [];
        for i in range(1,len(L)):
                k = ksubset(L,i);
                result.extend(k);
        
        return result;
#-----------------------------------------------------------------------------#
def main():
        a = [0,1,2];
        K = allsubsets(a);
        print K;
#-----------------------------------------------------------------------------#
if __name__ == '__main__':
        main();

위 코드를 C++로 옮기면 다음과 같을 것이다.

#include <string>

#include <vector>

#include <iostream>

 

std::vector<int> copy(const std::vector<int>& source, int *idx, int idx_length)

{

    std::vector<int> result;

    int i = 0;

    for(i = 0; i<idx_length; i++){

        result.push_back(source.operator[](idx[i]));

    }

 

    return result;

}

 

 

bool forward_index(int* idx, int idx_length, int max_length)

{

    int i = 0; int j = 0;

    for(i = idx_length - 1; i >= 0; i--){

        if(idx[i] == max_length - idx_length + i){

            continue;

        }

        else{

            // 이 부분이 위 그림에서 (1) 이라고 표현된 부분

            idx[i] = idx[i] + 1;

            for(j = i + 1; j<idx_length; j++){

                idx[j] = idx[j-1] + 1;

            }

            return true;

        }

    }

 

    return false;

}

 

bool ksubset(const std::vector<int>& source_set, int k, std::vector<std::vector<int> > *dest)

{

    if(source_set.empty() == true) return false;

    int src_length = (int)(source_set.size());

    if(k <= 0 || k > src_length) return false;

    if(src_length == k){

        dest->push_back(source_set);

        return true;

    }

 

    const int& max_length = src_length;

    int* idx = new int[k];

    int i = 0;

    for(i = 0; i<k; i++){

        idx[i] = i;

    }

    while(1){

        std::vector<int> subset = copy(source_set, idx, k);

        dest->push_back(subset);

        if(forward_index(idx, k, max_length) == false) break;

    }

 

    delete idx;

    return true;

}

 

bool allsubset(const std::vector<int>& source_set, std::vector<std::vector<int> >* dest)

{

    int length = (int)(source_set.size());

    int i = 0;

    for(i = 1; i<=length; i++){

        if(ksubset(source_set, i, dest) == false) return false;

    }

 

    return true;

}

 

int main(int argc, const char* argv[])

{

 

    std::vector<std::vector<int> > r;

    std::vector<int> s;

    s.push_back(0); s.push_back(1); s.push_back(2); s.push_back(3); s.push_back(4);

    //ksubset(s, 2, &r);

    allsubset(s, &r);

    int i = 0 ;

    std::vector<std::vector<int> >::const_iterator rpos = r.begin();

    for(; rpos != r.end(); rpos++,i++){

        std::vector<int>::const_iterator pos = rpos->begin();

        std::cout << i << ':';

        for(; pos != rpos->end(); pos++){

            std::cout << '\t' << *pos;

        }

        std::cout << std::endl;

    }

 

 

    return 0;

}

뭐, 효율성이나 코드의 aesthetics 따윈 보이지 않는, 참으로 날것의 코드 :) 어쨌거나 위에 나타난 기본적인 방법을 이용하면 좀 더 일반성 있는 코드 - 가령 iterator나 template을 이용하거나 - 나 좀 더 효율적인 코드(특히 파이썬 코드에서)를 작성하는 것에는 큰 어려움이 없을 것이다. 언제나 중요한 것은 idea 니까, 코딩 따위야 그냥 뭐 하면 되는 거지...

1. 수학의 증명에 보면 자주 나오는 말, 일반성을 잃지 않으면서 모든 수에 대해 확장해 보면, 이란 말. ㅋㅋㅋ 여기 나와 있는 생각도 사실 원소가 2개인 부분집합에서 아이디어를 따온 후, 곧바로 k 라는 일반적인 자연수로 확장을 시켰을 뿐 별다른 것이 없다. [본문으로]
2. 이런 부분을 여기서 설명해야 하나, 하는 궁금증이 있다. 1,2,3개 정도에서 되면 일반적인 n 으로 확장하는 것은 자주 접하던 일이라... 만약 이 부분이 명확하지 않다는 것을 알려 준다면 보충하겠습니다. [본문으로]