C++ Cartesian Product

이전 포스팅들에서도 소개한 Cartesian Product 를 C++ 를 사용하여 구성하는 방법에 대해 소개해 드리려 합니다.

  

2013/08/18 - [programming language/MATLAB] - MATLAB 모든 경우의 수 뽑기 Cartesian Product

2013/08/18 - [programming language/powershell] - Powershell 경우의 수 조합 다 구하기(Cartesian Product)

 

아래 주소를 보니 Cartesian Product 와 관련하여 좋은 예제들이 많이 있더군요.

 

http://stackoverflow.com/questions/5279051/how-can-i-create-cartesian-product-of-vector-of-vectors

 

그 중에서 저는 가장 간단해 보이는 anumi 라는 분의 코드를 가져다 사용했습니다.

 

물론 template 형태로 약간 수정만 했습니다.

 

코드를 보다 보니 vector 의 swap 함수를 사용했더군요. Swap 함수는 말 그대로 벡터간에 값을 교환하는 겁니다.

 

Vector 의 Swap 에 대한 설명은 아래 주소 참조바랍니다.

 

http://www.cplusplus.com/reference/vector/vector/swap/

 

요즘 C++ STL 은 정말 좋은 것 같습니다.

 

결과적으로 작성된 cartesian.h 파일은 아래와 같습니다. 

  

cartesian.h

#include <vector>

 

using namespace std;

 

template<typename T>

vector<vector<T>> cart_product (const vector<vector<T>>& v) {

vector<vector<T>> s = {{}};

for (auto& u : v) {

vector<vector<T>> r;

for (auto& x : s) {

for (auto y : u) {

r.push_back(x);

r.back().push_back(y);

}

}

s.swap(r);

}

return s;

}

 

테스트를 위한 main.cpp 파일은 아래와 같이 작성했습니다.

 

#include <iostream>

#include "cartesian.h"

 

using namespace std;

 

int main()

{

    vector<vector<int>> test{{1,2, 56 ,3}, {4,5,6}, {12,32,56}};

    vector<vector<int>> cartprodResult; // result

 

    cartprodResult=cart_product(test); // Cartesian Product

 

    int cnt=0;

 

    for (auto& x : cartprodResult)

    {

        ++cnt;

        cout << cnt << ": \t";

 

        for (auto y : x)

        {

            cout << y << "\t";

        }

        cout << endl;

    }

 

    return 0;

}

 

Cartesian product 를 수행해보면 아래와 같이 결과가 나오는 것을 확인 할 수 있습니다. 간단하죠~ 현재 컴파일러는 gcc (tdm64-2) 4.8.1 이고~ C++11 Compiler Flag를 On 했습니다.