C++ Permutation 함수

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

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

 C++ Permutation Overview

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

모든 순열(Permutation)을 가져온다.

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

b       c

c       b

a       c

c       a

a       b

b       a

비트셋 집합은 순서를 표현할 수 없으므로 논외이다.

 Function Usage

int main() {
    //! 벡터로 표현된 집합.
    vector<string> vset = {"a", "b", "c"};
    vector<vector<string>> all_permutation = get_permutations_from_vector(vset, 2);

    //! 각 순열을 출력.
    for(auto &permutation : all_permutation){
        for(auto &str : permutation){
            cout << str << '\t';
        }
        cout << '\n';
    }
}

 Implement

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

    //! 현재 가지고있는 요소의 위치를 삽입한다.
    //! vector<T> 에서는 모든 요소의 위치를 삽입한다.
    vector<int> index_mapper;
    for(auto i=0; 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=0;i<set.size()-pick_up;i++) combination_iterator.push_back(0);
    sort(combination_iterator.begin(), combination_iterator.end());

    //! 매 루프마다 조합을 조립한다.
    do {
        vector<int> this_combination_index;
        for(auto i=0; i<combination_iterator.size(); i++){
            if(combination_iterator[i]) {
                this_combination_index.push_back(index_mapper[i]);
            }
        }

        //! 이제 순열을 조합한다.
        sort(this_combination_index.begin(), this_combination_index.end());
        do {
            vector<T> this_combination;
            for(int idx : this_combination_index){
                this_combination.push_back(set[idx]);
            }
            permutations.push_back(this_combination);
        }while(next_permutation(this_combination_index.begin(), this_combination_index.end()));
    } while(next_permutation(combination_iterator.begin(), combination_iterator.end()));

    //! 완성된 순열의 배열을 반환한다.
    return permutations;
}