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;
}