안녕하세요! 지난 글들에서 우리는 파이썬 itertools의 다양한 기능—range, enumerate, zip, map, filter, chain, takewhile, dropwhile, accumulate, groupby—를 C++에서도 나름 “파이썬스럽게” 구현하거나 표현하는 방법을 두루 살펴봤습니다. 이번에는 itertools의 대표적인 조합론적(iteration over combinations) 함수들인 product, permutations, combinations를 살펴보려고 합니다.
이 함수들은 파이썬에서 꽤 자주 쓰입니다. 예를 들어 product([1,2],[3,4])는 (1,3), (1,4), (2,3), (2,4)를 만들어내고, permutations([1,2,3], 2)는 (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)를, combinations([1,2,3,4], 2)는 (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)를 내놓습니다.
C++에서도 이런 조합론적 반복 패턴을 구현할 수 있습니다. 물론 파이썬만큼 바로 쓸 수 있는 빌트인 함수는 없지만, C++20 이후로 제너레이터나 뷰를 활용하면 lazy하게 이터레이션을 제공하는 것이 생각보다 가능하답니다.
1. 일반적인 C++ 구현 (Before)
C++17까지, 이런 조합론적 문제를 해결하려면 보통 다음과 같은 방식으로 코딩했습니다.
- product: 중첩 for 루프나 재귀를 통해 모든 조합을 생성
- permutations: std::next_permutation 알고리즘 사용
- combinations: 이진 마스크(bitmask)나 재귀, 혹은 std::next_permutation 트릭 이용
예를 들어 product([1,2],[3,4])를 C++17 스타일로 만든다면:
#include <vector>
#include <iostream>
int main() {
std::vector<int> a = {1,2};
std::vector<int> b = {3,4};
for (auto x : a) {
for (auto y : b) {
std::cout << "(" << x << "," << y << ") ";
}
}
std::cout << "\n";
// 결과: (1,3) (1,4) (2,3) (2,4)
}
간단한 경우야 이렇게 하면 되지만, 컨테이너 개수가 늘어나거나, permutations나 combinations를 구현하려면 코드가 길어지고 복잡해집니다.
2. 단순한 Python 같은 C++ 구현 (After: 첫 단추)
여기서는 간단한 뷰(view)를 만들어 Python의 product를 흉내 내볼게요. 실제로는 variadic template를 써서 여러 컨테이너를 받는 product를 구현할 수도 있지만, 일단은 두 컨테이너를 대상으로 하는 간단한 예시로 출발해보겠습니다.
product_view (2개 컨테이너용)
template<typename C1, typename C2>
class product_view {
public:
product_view(C1& c1, C2& c2) : c1_(c1), c2_(c2) {}
class iterator {
public:
using it1_type = decltype(std::begin(std::declval<C1&>()));
using it2_type = decltype(std::begin(std::declval<C2&>()));
iterator(it1_type it1, it1_type end1, it2_type it2, it2_type begin2, it2_type end2)
: it1_(it1), end1_(end1), it2_(it2), begin2_(begin2), end2_(end2) {}
iterator& operator++() {
++it2_;
if (it2_ == end2_) {
it2_ = begin2_;
++it1_;
}
return *this;
}
bool operator!=(const iterator& other) const {
return it1_ != other.it1_ || it2_ != other.it2_;
}
auto operator*() const {
return std::pair{*it1_, *it2_};
}
private:
it1_type it1_, end1_;
it2_type it2_, begin2_, end2_;
};
auto begin() {
return iterator(std::begin(c1_), std::end(c1_), std::begin(c2_), std::begin(c2_), std::end(c2_));
}
auto end() {
return iterator(std::end(c1_), std::end(c1_), std::end(c2_), std::begin(c2_), std::end(c2_));
}
private:
C1& c1_;
C2& c2_;
};
template<typename C1, typename C2>
auto product_func(C1& c1, C2& c2) {
return product_view<C1,C2>(c1,c2);
}
사용 예제:
#include <vector>
#include <iostream>
int main() {
std::vector<int> a = {1,2};
std::vector<int> b = {3,4};
for (auto [x,y] : product_func(a,b)) {
std::cout << "(" << x << "," << y << ") ";
}
std::cout << "\n";
// (1,3) (1,4) (2,3) (2,4)
}
이렇게 하면 파이썬의 product([1,2],[3,4])와 유사한 느낌을 낼 수 있습니다.
permutations 구현 (간단한 예)
permutations는 std::next_permutation을 활용하면 간단히 만들 수 있습니다. std::next_permutation은 주어진 범위를 사전순으로 순회하는 알고리즘이죠. 여기서는 벡터를 복사해서 모든 순열을 하나씩 반환하는 뷰를 대충 구현해볼게요. 다만 이는 lazy하지 않고, 각 순열을 복사 생성하므로 성능은 조금 떨어질 수 있습니다.
#include <algorithm>
#include <vector>
template<typename Container>
class permutations_view {
public:
permutations_view(const Container& c, std::size_t r = 0)
: original_(c), r_(r ? r : c.size()) {
// r이 지정 안 되면 전체 길이
comb_.reserve(original_.size());
comb_.insert(comb_.end(), original_.begin(), original_.end());
std::sort(comb_.begin(), comb_.end());
end_ = !comb_.empty();
}
class iterator {
public:
iterator(permutations_view* parent, bool end)
: parent_(parent), end_(end) {}
iterator& operator++() {
// 다음 순열로 이동
if (!std::next_permutation(parent_->comb_.begin(), parent_->comb_.end())) {
end_ = true;
}
return *this;
}
bool operator!=(const iterator& other) const { return end_ != other.end_; }
auto operator*() const {
// 앞에서 r개만 반환
return std::vector<typename Container::value_type>(parent_->comb_.begin(), parent_->comb_.begin() + parent_->r_);
}
private:
permutations_view* parent_;
bool end_;
};
auto begin() {
return iterator(this, !end_);
}
auto end() {
return iterator(this, true);
}
private:
Container original_;
std::vector<typename Container::value_type> comb_;
std::size_t r_;
bool end_;
};
template<typename Container>
auto permutations_func(const Container& c, std::size_t r = 0) {
return permutations_view<Container>(c, r);
}
사용 예제:
std::vector<int> arr = {1,2,3};
for (auto perm : permutations_func(arr, 2)) {
for (auto x : perm) std::cout << x << " ";
std::cout << "\n";
}
// 출력 (정렬 후 사전순):
// 1 2
// 1 3
// 2 1
// 2 3
// 3 1
// 3 2
이 예제는 완벽히 파이썬 permutations와 동일하진 않지만, 개념은 비슷합니다. 더 정교한 구현을 하면 lazy하게 next_permutation을 호출하면서 값 하나씩 반환하거나, iterator를 변형할 수도 있습니다.
combinations 구현 (간단한 예)
combinations는 r 길이의 조합을 생성합니다. 간단한 방식으로는 이진 마스크나 재귀를 사용할 수 있습니다. 여기서는 이진 마스크를 사용해 모든 조합을 만들어내는 단순한 뷰를 보여줄게요. 이 역시 lazy하지 않고, 각 조합을 매번 벡터로 만들어 반환합니다.
template<typename Container>
class combinations_view {
public:
combinations_view(const Container& c, std::size_t r)
: c_(c), r_(r), mask_(0) {
// 초기 마스크: 앞의 r 비트를 1로 세팅 (ex: r=2, mask=...11)
mask_ = (1ULL << r_) - 1ULL;
end_ = (r_ > c.size());
}
class iterator {
public:
iterator(const Container* c, std::size_t r, unsigned long long mask, bool end)
: c_(c), r_(r), mask_(mask), end_(end) {}
iterator& operator++() {
// 다음 조합 찾기 (bit trick)
// Gosper's hack (다음 조합 마스크) 사용하거나 next_permutation(bitset) 로직
unsigned long long u = mask_ & (-mask_);
unsigned long long v = u + mask_;
if (v == 0) { end_ = true; return *this; }
mask_ = v + (((v ^ mask_) >> 2) / u);
if (mask_ >= (1ULL << c_->size())) end_ = true;
return *this;
}
bool operator!=(const iterator& other) const { return end_ != other.end_ || mask_ != other.mask_; }
auto operator*() const {
std::vector<typename Container::value_type> comb;
for (std::size_t i = 0; i < c_->size(); ++i) {
if (mask_ & (1ULL << i)) {
comb.push_back((*c_)[i]);
}
}
return comb;
}
private:
const Container* c_;
std::size_t r_;
unsigned long long mask_;
bool end_;
};
auto begin() {
return iterator(&c_, r_, mask_, end_);
}
auto end() {
return iterator(&c_, r_, 0, true);
}
private:
const Container& c_;
std::size_t r_;
unsigned long long mask_;
bool end_;
};
template<typename Container>
auto combinations_func(const Container& c, std::size_t r) {
return combinations_view<Container>(c, r);
}
사용 예제:
std::vector<int> arr2 = {1,2,3,4};
for (auto comb : combinations_func(arr2, 2)) {
for (auto x : comb) std::cout << x << " ";
std::cout << "\n";
}
// 출력 (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)
3. 정교한(또는 확장된) 구현: C++20 Ranges와 Concepts 활용
C++20 Ranges, Concepts를 활용하면 다음과 같은 이점이 있습니다.
- Concepts로 product, permutations, combinations에 들어가는 컨테이너들이 순회 가능한지, 정렬 가능한지, 비교 가능한지 등을 제약할 수 있습니다.
- Lazy evaluation과 파이프라인 결합: data | product(other) | filter(...) | transform(...) 식으로 체인할 수 있습니다.
- range-v3 라이브러리나 다른 확장 라이브러리를 사용하면 더 깔끔하고 확장성 높은 구현이 가능합니다.
아직 표준 라이브러리에 product, permutations, combinations에 대응하는 뷰가 들어있지 않지만, range-v3나 다른 커뮤니티 라이브러리에서 유사 기능을 제공하는 경우가 있을 수 있습니다. 또한 C++23 이후로도 Ranges 관련 표준 확장이 계속 기대되므로, 미래에는 이런 기능들이 표준 라이브러리에서 구현될 가능성도 있습니다.
성능과 메모리 측면
- 현재 예제 구현들은 대부분 결과를 임시 벡터로 생성하므로 진정한 의미의 lazy evaluation이라고 보긴 어렵습니다.
- 보다 정교하게 구현하면 iterator만을 반환하거나, 다음 조합/순열을 계산할 때 필요 최소한의 작업만 수행하는 lazy한 접근이 가능합니다.
- product의 경우는 단순 반복자 증감과 비교만으로 처리 가능하므로 성능 오버헤드가 적습니다.
- permutations와 combinations의 구현 방식에 따라 성능 차이가 클 수 있지만, 작은 입력에 대해서는 충분히 실용적입니다.
관련 링크 및 리소스
- C++ 표준 문서:
- range-v3:
- range-v3 GitHub
일부 예제나 extension에서 permutations, combinations와 유사한 기능 구현 가능성 검토.
- range-v3 GitHub
- 파이썬 itertools 문서:
마무리
이번 글에서는 파이썬 itertools의 product, permutations, combinations를 C++20/23 스타일로 흉내내는 방법을 살펴봤습니다. 단순한 구현 예제를 통해 기본 개념을 짚어보았으며, Ranges와 Concepts를 활용하면 더 깔끔하고 타입 안전한 코드를 만들 수 있음을 강조했습니다. 물론 모든 기능을 완벽히 파이썬처럼 구현하는 건 쉽지 않지만, C++도 현대화된 기능을 잘 활용하면 “파이썬스러운” 코딩 경험에 조금씩 다가갈 수 있다는 점, 이제 어느 정도 느끼셨을 거라 생각합니다.