Nagie's DevStory
[ALGORITHM] 14. 순열 만들기 본문
728x90
순열 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 3개의 서로 다른 공에 대한 총 6가지의 순열 루빅스 큐브의 면에 대한 회전은 그 면의 9개의 부분에 대한 한 가지 순열이다. 수학에서 순열(順列, 문화어: 차례무
ko.wikipedia.org
사전적인 의미는 굳이 내가 작성하는 것 보단 위키피디아를 참고하는 게 더 나을 거 같아 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