Related to: Algorithm
설명
기본적으로 next_premutation을 사용하여 순열을 만들 경우, n개의 원소 중 n개를 뽑게 된다.(nPn)하지만 약간의 코드가 추가된다면 nPr연산이 가능하다.배열 A = {1,2,3,4,5} 일 때, next_permutation을 사용하여 순열을 만든다면 아래와 같이 진행된다.
loop 0: 12345loop 1: 12354loop 2: 12435loop 3: 12453loop 4: 12534loop 5: 12543loop 6: 13245loop 7: 13254loop 8: 13425loop 9: 13452…(생략)
하지만 r+1번째 부터 ~ n번째 까지의 원소를 뒤집어 버린다면 어떻게 될까?
loop 0: 12345 → 12354loop 1: 12435 → 12453loop 2: 12534 → 12543…(생략)
r+1번째 부터 n번째 까지의 원소를 뒤집어 버림으로써 첫 번째부터 r번째의 원소가 업데이트 될 수 밖에 없어진다.
header
\#include <algorithm>example
\#include <iostream>
\#include <vector>
\#include <algorithm>
using namespace std;
int main(){
vector<int> v = {3, 1, 2, 4, 5};
sort(v.begin(), v.end()); // v : {1,2,3,4,5}
do
{
for(int e : v) cout << e << " ";
cout << '\n';
reverse(v.begin() + r, v.end());
}while(next_permutation(v.begin(),v.end()));
return 0;
}