Related to: Algorithms
설명
기본적으로 next_permutation을 사용하여 순열을 만들 경우, 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번째의 원소가 업데이트 될 수 밖에 없어진다.
예시 / 코드
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;
}