next permutation 기본형은 아래와 같다. 배열(벡터)의 다음 사전순 순서를 반환해준다.
1, 2, 3 ,4를 이용해서 만들 수 있는 모든 길이 4짜리 수열을 만드는 코드는 아래와 같다. (순서가 다르면 다른 수열)
#include<iostream> #include<algorithm> using namespace std; int main(void) { int a[4] = { 1,2,3,4 }; do { for (int i = 0; i < 4; i++) cout << a[i] << ' '; cout << '\n'; } while (next_permutation(a, a + 4)); return 0; }
실행 결과는 위와 같다.
다음으로 6개의 숫자 중에서 2개의 숫자를 조합으로 뽑는 경우는 다음과 같다.
#include<iostream> #include<algorithm> using namespace std; int main(void) { int a[6] = { 1,5,3,6,2,7 }; //sort(a, a + 6); int Select[6] = { 0,0,1,1,1,1 }; //이러면 조합 int cnt = 0; do { cnt++; for (int i = 0; i < 6; i++) if (!Select[i]) cout << a[i] << ' '; cout << '\n'; } while (next_permutation(Select, Select + 6)); //cout << cnt; return 0; }
Select 배열을 가지고 next_permutation을 돌려준다. 뽑고 싶은 숫자의 개수를 0의 개수로 하고 앞에서부터 0을 써주면 된다. 위의 예시는 정렬을 하지 않았는데, 사용할 수 있는 숫자를 그대로 두고 실행했을 때 어떤 결과가 나오는지 보기 위함이다.
sorting하는 부분의 주석을 풀면, 사전순으로 수열이 정렬되서 나올 것이다.
이제 순열을 구현해보면 다음과 같다. 먼저 배열이 하나 더 필요하다. Select의 값이 0보다 클 때 if문에 진입하게 되고,
Select 값으로 index를 맞춰야 하는데 1부터 시작하므로 1씩 빼서 seq에 담아준 것이다.
#include<iostream> #include<algorithm> using namespace std; int main(void) { int a[6] = { 1,5,3,6,2,7 }; //sort(a, a + 6); int Select[6] = { 0,0,0,0,1,2 }; int cnt = 0; do { //cnt++; int seq[2] = {}; for (int i = 0; i < 6; i++) if (Select[i]) seq[Select[i] - 1] = a[i]; for (int i = 0; i < 2; i++) cout << seq[i] << ' '; cout << '\n'; } while (next_permutation(Select, Select + 6)); //cout << cnt; return 0; }
'Programming Language > C++' 카테고리의 다른 글
string 대소문자 변환 (0) | 2019.08.25 |
---|---|
priority_queue (0) | 2019.08.14 |
(C++) abs 함수의 사용 (0) | 2019.08.07 |
(C++) list STL 출력 및 iterator (0) | 2019.08.04 |
vector reverse (0) | 2019.07.04 |