C++ Combination 함수

해당 포스트 대신, 아래의 포스트를 사용해주세요.

[코딩테스트 대비] 순열 및 조합 알고리즘

 C++ Combination Overview

어떤 집합에서 r개를 선택하여 얻을 수 있는,

모든 조합(Combination)을 가져온다.

예를 들어,  벡터 집합 = {"a", "b", "d"}  에서 2개를 선택하여 얻을 수 있는 조합은 다음과 같다.

b       d

a       d

a       b

다른 예로,  비트셋 집합 =  0b1101 에서 2개를 선택하여 얻을 수 있는 조합은 다음과 같다.

1100

1001

0101

비트셋을 이용한 집합의 표현은 다음 게시글을 참고하기 바란다.

비트셋으로 집합 표현하기 (Bitset)

 

 Function Usage

• 벡터로 표현된 집합의 조합

int main() {
    //! 벡터로 표현된 집합.
    vector<string> vset = {"a", "b", "c"};
    vector<vector<string>> all_combination = get_combinations_from_vector<string>(vset, 2);
    for (auto combination : all_combination) {
        for (int i = 0; i < combination.size(); i++) {
            cout << combination[i] << '\t';
        }
        cout << '\n';
    }
}

• 비트셋으로 표현된 집합의 조합

int main() {
    //! 비트셋으로 표현된 집합.
    const int N = 4;
    bitset<N> bset(0b1101);
    vector<bitset<N>> all_combination = get_combinations_from_bitset<N>(bset, 2);
    for(auto combination : all_combination){
        cout << combination << '\n';
    }
}

 Implement - 벡터로 표현된 집합의 조합

/**
 * 해당 벡터에서 가능한 모든 조합을 가져온다.
 *
 * @tparam T        벡터가 담고있는 자료형.
 * @param set       벡터로 표현된 그룹.
 * @param pick_up   조합의 크기.
 * @return 가능한 모든 조합의 배열.
 *
 * @author https://aerocode.net
 */
template <typename T>
vector<vector<T>> get_combinations_from_vector(vector<T> set, int pick_up){
    //! 요소의 개수가 조합의 크기보다 작다면 조합은 실패한다.
    vector<vector<T>> combinations;
    if(set.size() < pick_up) throw exception();

    //! 현재 가지고있는 요소의 위치를 삽입한다.
    //! vector<T> 에서는 모든 요소의 위치를 삽입한다.
    vector<int> index_mapper;
    for(auto i=0ULL; i<set.size(); i++) index_mapper.push_back(i);

    //! 조합을 위한 이터레이터를 선언한다.
    vector<int> combination_iterator;
    for(auto i=0;i<pick_up;i++) combination_iterator.push_back(1);
    for(auto i=0ULL;i<set.size()-pick_up;i++) combination_iterator.push_back(0);
    sort(combination_iterator.begin(), combination_iterator.end());

    //! 매 루프마다 조합을 조립한다.
    do {
        vector<T> this_combination;
        for(auto i=0ULL; i<combination_iterator.size(); i++){
            if(combination_iterator[i]) {
                this_combination.push_back(set[index_mapper[i]]);
            }
        }
        combinations.push_back(this_combination);
    } while(next_permutation(combination_iterator.begin(), combination_iterator.end()));

    //! 완성된 조합의 배열을 반환한다.
    return combinations;
}

 Implement - 비트셋으로 표현된 집합의 조합

/**
 * 해당 비트셋에서 가능한 모든 조합을 가져온다.
 *
 * @tparam N        비트셋의 크기.
 * @param set       비트셋으로 표현된 그룹.
 * @param pick_up   조합의 크기.
 * @return 가능한 모든 조합의 배열.
 *
 * @author https://aerocode.net
 */
template <int N>
vector<bitset<N>> get_combinations_from_bitset(bitset<N> set, int pick_up){
    //! 요소의 개수가 조합의 크기보다 작다면 조합은 실패한다.
    vector<bitset<N>> combinations;
    if(set.count() < pick_up) throw exception();

    //! 현재 가지고있는 요소의 위치를 삽입한다.
    //! bitset 에서는 1로 설정된 위치만 삽입한다.
    vector<int> index_mapper;
    for(int i=0; i<N; i++) {
        if(set[i]) index_mapper.push_back(i);
    }

    //! 조합을 위한 이터레이터를 선언한다.
    vector<int> combination_iterator;
    for(int i=0;i<pick_up;i++) combination_iterator.push_back(1);
    for(int i=0;i<set.count()-pick_up;i++) combination_iterator.push_back(0);
    sort(combination_iterator.begin(), combination_iterator.end());

    //! 매 루프마다 조합을 조립한다.
    do {
        bitset<N> this_combination;
        for(auto i=0ULL; i < combination_iterator.size(); i++){
            if(combination_iterator[i]) {
                this_combination.set(index_mapper[i]);
            }
        }
        combinations.push_back(this_combination);
    }
    while(next_permutation(combination_iterator.begin(), combination_iterator.end()));

    //! 완성된 조합의 배열을 반환한다.
    return combinations;
}