Nagie's DevStory
[ALGORITHM] 14. 순열 만들기 본문
728x90
사전적인 의미는 굳이 내가 작성하는 것 보단 위키피디아를 참고하는 게 더 나을 거 같아 URL을 첨부한다.
아래는 재귀함수를 사용한 순열 생성 코드이다.
template<typename T>
void print_vec(const std::vector<T>& vec) {
for (const auto& e : vec) {
std::cout << e << " ";
}
std::cout << std::endl;
}
void permutation(std::vector<int>& vec,int k) {
if (k == vec.size() - 1) {
print_vec(vec);
return;
}
for (int i = k; i < vec.size(); i++) {
std::swap(vec[k], vec[i]);
permutation(vec, k + 1);
std::swap(vec[k], vec[i]);
}
}
위처럼 구현하는 것 말고도 C++ STL에서 제공하는 std::next_permutation()을 사용해 간단하게 코드를 작성할 수 있다.
std::sort(vec.begin(), vec.end());
do {
print_vec(vec);
} while (std::next_permutation(vec.begin(), vec.end()));
다만 위의 코드를 사용하려면 C++에서 제공하는 <algorithm> 헤더를 소스에 포함해 줘야 한다.
728x90
Comments