순열(Permutation): C++ next_permutation: nPr 순열 구하기

HyeongSeok Kim·2022년 8월 16일
0

Algorithm

목록 보기
3/8

참조

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>

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;
}
profile
Computer Vision & SW Engineer

0개의 댓글