[C++] next_permutation으로 STL Combination 함수 작성하기

학교 과제를 하던 중, Combination(조합)을 구현할 일이 생겼습니다. Permutation(순열)은 std::next_permutation으로 이미 라이브러리가 있고, Combination도 간단히 정수형이나 실수형 등에 대해서는 Stackoverflow등이나 다른 블로그에서 소개한 글들을 쉽게 찾을 수 있었지만, 일반화된 Combination함수는 찾기 어렵더라고요. 이번 포스트에서는 Template을 이용해, 일반화된 Combination 함수를 구현하도록 하겠습니다. 간단한 구현을 위해 std::next_permutation 함수를 이용합니다. 

글쓰기에 앞서, 모든 내용은 https://twpower.github.io/90-combination-by-using-next_permutation 블로그 포스팅을 참고했습니다. 이 포스트는 해당 블로그의 내용을 좀 더 풀어쓰고 STL로 일반화시킴을 목표로 합니다.

작성하는 Combination 라이브러리는 다음을 목표로 합니다 :

- 어떤 자료구조와 r 값을 입력받아, nCr에 해당하는 모든 조합을 2차원 vector로 반환한다.

std::next_permutation

STL의 <algorithm>에서 C++11이후에 제공되는 라이브러리 중 std::next_permutation 함수가 있습니다. 조건을 만족하는 임의의 자료구조를 받아, 다음 순서에 해당하는 permutation으로 자료구조를 조작해주는 함수인데요, 함수의 정의는 다음과 같습니다.

template <class BidirectionalIterator>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);

반환값은 bool 타입으로, 더이상 다음 순열을 찾을 수 없을 때 false를 반환합니다. 정렬 순서는 operator< 연산을 이용합니다.

인자로는 양방향 반복자의 시작과 끝을 넣어주면 됩니다. 양방향 반복자에 대해 이야기했는데, 간단하게 iterator중 ++, -- 연산을 모두 지원하는 반복자를 가리킵니다. 자세한 것은 나중에 기회가 있을 때 다루기로 하고, 여기서는 std::vector, std::deque, std::set 정도만 next_permutation을 이용할 수 있고 std::forward_list는 이용할 수 없다 정도로 알아둡시다. 참고로 일반 배열도 시작주소와 끝 주소의 제공을 통해, next_permutation을 활용할 수 있습니다.

next_permutation는 다음과 같이 사용할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
 
using std::vector;
using std::string;
using std::cout;
 
int main() {
    vector<int> intVec{ 1,2,3 };
    
    //모든 permutation을 얻기 위해 정렬이 필요하다.
    std::sort(intVec.begin(), intVec.end());
    
    //bool값을 반환할 때까지 반복한다.
    do {
        for (auto it = intVec.begin(); it != intVec.end(); ++it)
            std::cout << *it << ' ';
        std::cout << std::endl;
    } while (std::next_permutation(intVec.begin(), intVec.end()));
}

실행결과 :

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

모든 순열을 얻기 위해서는, next_permutation을 쓰기 전에 주의할 점이 두가지 있습니다. 첫 번째는 시작 전에std::sort를 사용해야 한다는 점입니다. next_permutation은 단순히 인자로 넘어왔을 때의 상황만 보고, 다음 순서에 해당하는 순열을 반환해주기 때문에 정렬되지 않은 container를 조작할 때에는 모둔 순열을 반환받을 수 없습니다.

두 번째는 반복문 내에서 자료구조를 조작하면 안됩니다. 여기서 조작이라 하면 원소를 추가한다던가, swap한다던가, 원소를 없애거나, 값을 변경하는 행위를 가리킵니다. 오직 Read-only로만 사용해야, next_permutation이 일관성있게 동작합니다. 첫 번째 이유와 같은 맥락이니, 잘 이해가 되지 않는 다면 next_permutation을 반복호출하는 이유를 생각해보시면 금방 알 수 있을 것입니다.

Permutation과 Combination

Combination은 permutation과의 관계를 이용해 구현합니다. 목표는, 어떤 수열에서 다음을 만족하는 모든 조합을 찾아내는 것입니다. 다음과 같은 수열이 있다고 합시다. 

수열 : 1, 2, 3, 4, 5
목표 : 5C3

이 경우 목표 조합은

1, 2, 3
1, 2, 4
1, 2, 5
1, 3, 4
1, 3, 5
1, 4, 5
2, 3, 4
2, 3, 5
2, 4, 5
3, 4, 5

가 되겠죠. 이를 구하기 위해, 다음과 같은 보조 수열을 생각합시다.

보조수열 : 0, 0, 1, 1, 1

중요한 점은 1의 개수를 r만큼 두고, 나머지를 0으로 두는 것입니다.

이 보조수열의 순열을 구해봅시다(5P5). 단, 중복은 제외합니다. 

0, 0, 1, 1, 1
0, 1, 0, 1, 1
0, 1, 1, 0, 1
0, 1, 1, 1, 0
1, 0, 0, 1, 1
1, 0, 1, 0, 1
1, 0, 1, 1, 0
1, 1, 0, 0, 1
1, 1, 0, 1, 0
1, 1, 1, 0, 0

5P5 순열을 구하며 중복을 제외했기 때문에, 결과적으로는 숫자 1의 분포가 모두 다른 순열이 구해졌습니다. 순열이 총 10개인데, 이는 5C3 = 10의 값과 일치합니다. 이를 본 수열과 비교해봅시다.

1, 2, 3, 4, 5
-------------
0, 0, 1, 1, 1
0, 1, 0, 1, 1
0, 1, 1, 0, 1
0, 1, 1, 1, 0
1, 0, 0, 1, 1
1, 0, 1, 0, 1
1, 0, 1, 1, 0
1, 1, 0, 0, 1
1, 1, 0, 1, 0
1, 1, 1, 0, 0

핵심은, 숫자 1의 위치에 있는 원소만 추출하는 것입니다. 그렇게 하면 다음과 같은 최종 조합을 얻을 수 있습니다.

 

1, 2, 3, 4, 5
-------------
      3, 4, 5
   2,    4, 5
   2, 3,    5
   2, 3, 4
1,       4, 5
1,    3,    5
1,    3, 4
1, 2,       5
1, 2,    4
1, 2, 3 

정리하면, 다음과 같습니다.

1. nCr에 대해, 전체길이가 n, 1의 개수가 r, 나머지가 0으로 채워진 보조 수열을 생성한다.

2. 보조 수열에 대한 순열을 모두 구한다. 이때 중복을 제외한다.

3. 보조 수열의 결과 순열을 모두 조사하여, 값이 1인 위치(인덱스)를 찾아 원래 자료구조에서 추출한다.

C++로 구현하기 - 1. template으로 함수 시그니처 설정하기

C++로 구현하기 위해 가장 골치아픈 점은 바로 인자를 받는 방법입니다. 먼저 template을 이용하여 임의의 Container를 받을 수 있습니다.

template <typename Container_>

nCr의 형태에 맞춰 함수의 정의를 더 완성합니다.

template <typename Container_>
리턴값 Combination(const Container_& container, int r){}

중요한 점은 리턴값의 형태를 정하는 방법입니다. 저는 결과 순열 하나하나를 vector에 저장할 것이며, 그러한 vector를 모두 모아 반환할 것입니다. 따라서 2차원 벡터가 반환되어야 합니다. 다음과 같이 리턴값을 작성합니다.

template <typename Container_>
std::vector<std::vector<컨테이너가 저장하는 자료형> 
    Combination(const Container_& container, int r){}

여기서 새로운 문제가 등장합니다. '컨테이너가 저장하는 자료형'을 어떻게 정의할 것인가?

간단한 설명을 위해 잠깐 visual studio 2017의 자동완성 기능을 이용해 봅시다. 

 

위 사진을 통해 알 수 있는 사실인데요, vector나 deque등의 STL Container에서는 ::(범위지정연산자)를 통해 내부에서 사용하는 value_type을 추론할 수 있습니다. 이를 이용해 정의부를 개량합시다.

template <typename Container_>
std::vector<std::vector<Container_::value_type> 
    Combination(const Container_& container, int r){}

문제는, 실제로 저 함수를 컴파일 하면 다음과 같은 메세지가 뜹니다.

따라서 다음과 같이 함수 시그니처를 수정합니다. 컴파일러가 함수의 정의부를 처리하기 전, 미리 템플릿 파라미터부분에서 value_type을 처리하는 방법입니다.

template <typename Container_, typename value_type = Container_::value_type>
std::vector<std::vector<value_type> 
    Combination(const Container_& container, int r){}

C++로 구현하기 - 2. 함수 정의 작성하기

먼저 n의 값을 구합니다.

int n = container.size();

r < 0인 경우와 n< r인 경우를 예외처리합니다.

if (n < r) return {};
if (r < 0) return {};

return {}의 의미는 return std::vector<std::vector<value_type>>({})와 같습니다. 즉, 빈 벡터를 반환합니다.

반환용으로 사용할 2차원 백터와, 임시로 사용할 백터를 선언합니다.

std::vector<std::vector<value_type> >totVec;//return 2d-vector
std::vector<value_type> tempVec(r);//saves temporary combination

tempVec(r)은 tempVec의 크기를 미리 r만큼 잡아둔다는 의미입니다.

보조 수열을 선언합니다. bool 벡터를 사용하며, False < True이므로 0, 0, 1, 1, 1...과 같이 선언합니다. 이렇게하면 굳이 sort를 부르지 않더라도 정렬되어있는 배열이 됩니다.

std::vector<bool> v(n);
std::fill(v.end() - r, v.end(), true);

마지막으로, 위의 1~3을 수행하는 코드를 작성합니다. 

int idx;
do {
    idx = 0;
    for (int i = 0; i < n; ++i) {
        if (v[i]) {
            tempVec[idx++] = *(container.begin() + i);
        }
    }
    totVec.push_back(tempVec);
} while (std::next_permutation(v.begin(), v.end()));
return totVec;

if (v[i]) 문이 바로 보조수열의 원소값이 1일 때 Container에서 원소값을 추출하는 코드입니다. for문을 통해 한 조합을 생성해낸 다음, totVec에 해당 벡터를 추가합니다.

사실 if문 안에서 원소를 복사하는 것이 오버헤드입니다. 같은 원소가 tempVec에 복사되고, 마지막에 totVec에 또 복사되기 때문이죠. return totVec;까지 생각하면, 사실 같은 원소가 3번이나 복사가 되고 있습니다. 성능 최적화다 필요하시다면 저 부분을 수정하여 사용하시길 바랍니다.

최종 코드는 다음과 같습니다. Visual Studio 2017에서 테스트를 수행했습니다.

<Combination.h>

#pragma once
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
 
template<typename Container_, typename value_type = Container_::value_type>
std::vector<std::vector<value_type> > Combination(Container_ container, int r) {
    int n = container.size();
    if (n < r) return {};
    if (r < 0) return {};
 
    std::vector<std::vector<value_type> >totVec;//return 2d-vector
    std::vector<value_type> tempVec(r);//saves temporary combination
 
    std::vector<bool> v(n);
    std::fill(v.end() - r, v.end(), true);
    int idx;
    do {
        idx = 0;
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                tempVec[idx++] = *(container.begin() + i);
            }
        }
        totVec.push_back(tempVec);
    } while (std::next_permutation(v.begin(), v.end()));
 
    return totVec;
}
 

사용 예도 함께 올립니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include "Combination.h"
 
using std::vector;
using std::string;
using std::cout;
using std::endl;
 
int main() {
    vector<int> intVec{3, 2, 5, 1, 5};
    vector<string> strVec{ "Apple", "Banana", "Car" };
 
    //intVec에 대해 3C2 수행
    for (auto& vec : Combination(intVec, 2)) {
        for (auto& ele : vec)
            std::cout << ele << ' ';
        cout << endl;
    }
    cout << endl;
 
    //strVec에 대해 3C2 수행
    for (auto& vec : Combination(strVec, 2)) {
        for (auto& ele : vec)
            cout << ele << ' ';
        cout << endl;
    }
}
 

수행결과 -

1 5
5 5
5 1
2 5
2 1
2 5
3 5
3 1
3 5
3 2
 
Banana Car
Apple Car
Apple Banana