[Algorithm] C++에서 next_permutation 함수(혹은 prev_permutation 함수)를 통해서 순열 구하기
업데이트(2018.03.14): 함수 사용법을 분리하여 조금 더 상세하게 작성하였습니다.
C++에서 next_permutation 함수 혹은 prev_permutation 함수를 통해서 순열을 구해보는 방법
환경 및 선수조건
- C++ 및 STL의 사용법(iterator)
함수
STL에 algorithm 헤더파일을 추가하면(#include <algorithm>) 다음 아래 함수를 통해서 순열을 구할수가 있다.
함수에 벡터의 iterator 혹은 배열의 주소를 넣으면 다음 순열(1-2-3-4의 다음 순열은 1-2-4-3) 혹은 이전 순열(1-2-4-3의 이전 순열은 1-2-3-4)의 결과가 벡터나 배열에 적용된다.
next_permutation: 현재 나와 있는 수열에서인자로 넘어간범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.prev_permutation: 현재 나와 있는 수열에서인자로 넘어간범위에 해당하는 이전 순열을 구하고 true를 반환한다. 이전 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 크다면) false를 반환.
next_permutation 함수
기본 구조
// 첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);
// 아래처럼 직접 비교함수를 넣어줘도 됩니다.
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);
사용법
순열을 구하고 싶은 1-2-3-4의 배열이 있다고 가정을 하면 next_permutation의 함수를 사용하면 배열의 값들이 다음 순열인1-2-4-3로 바뀌고 함수는 true를 반환합니다.
구현 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
// 1부터 4까지 저장할 벡터 선언
// 배열도 가능!
vector<int> v(4);
// 1부터 4까지 벡터에 저장
for(int i=0; i<4; i++){
v[i] = i+1;
}
// next_permutation을 통해서 다음 순열 구하기
do{
for(int i=0; i<4; i++){
cout << v[i] << " ";
}
cout << '\n';
}while(next_permutation(v.begin(),v.end()));
return 0;
}
구현 결과
1 2 3 4
1 2 4 3
1 3 2 4
...
4 2 3 1
4 3 1 2
4 3 2 1
prev_permutation 함수
기본 구조
// 첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝
bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last);
// 아래처럼 직접 비교함수를 넣어줘도 됩니다.
bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);
사용법
순열을 구하고 싶은 4-3-2-1의 배열이 있다고 가정을 하면 prev_permutation의 함수를 사용하면 배열의 값들이 다음 순열인4-3-1-2로 바뀌고 함수는 true를 반환합니다.
구현 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
// 1부터 4까지 저장할 벡터 선언
// 배열도 가능!
vector<int> v(4);
// 4부터 1까지 벡터에 저장
for(int i=0; i<4; i++){
v[i] = 4-i;
}
// prev_permutation을 통해서 이전 순열 구하기
do{
for(int i=0; i<4; i++){
cout << v[i] << " ";
}
cout << '\n';
}while(prev_permutation(v.begin(),v.end()));
return 0;
}
구현 결과
4 3 2 1
4 3 1 2
4 2 3 1
...
1 3 2 4
1 2 4 3
1 2 3 4