https://velog.io/@tiryul/순열-Permutation-C-Algorithm-nextpermutation-사용법
기본적으로 next_premutation을 사용하여 순열을 만들 경우, n개의 원소 중 n개를 뽑게 된다.(nPn)
하지만 약간의 코드가 추가된다면 nPr연산이 가능하다.
배열 A = {1,2,3,4,5} 일 때, next_permutation을 사용하여 순열을 만든다면 아래와 같이 진행된다.
loop 0: 12345
loop 1: 12354
loop 2: 12435
loop 3: 12453
loop 4: 12534
loop 5: 12543
loop 6: 13245
loop 7: 13254
loop 8: 13425
loop 9: 13452
. . .(생략)
하지만 r+1번째 부터 ~ n번째 까지의 원소를 뒤집어 버린다면 어떻게 될까?
loop 0: 12345 -> 12354
loop 1: 12435 -> 12453
loop 2: 12534 -> 12543
. . .(생략)
r+1번째 부터 n번째 까지의 원소를 뒤집어 버림으로써 첫 번째부터 r번째의 원소가 업데이트 될 수 밖에 없어진다.
#include <algorithm>
#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;
}