[Algorithm] C++에서 next_permutation 함수(혹은 prev_permutation 함수)를 통해서 순열 구하기

업데이트(2018.03.14): 함수 사용법을 분리하여 조금 더 상세하게 작성하였습니다.

C++에서 next_permutation 함수 혹은 prev_permutation 함수를 통해서 순열을 구해보는 방법


환경 및 선수조건

  • C++ 및 STL의 사용법(iterator)


함수

STL에 algorithm 헤더파일을 추가하면(#include <algorithm>) 다음 아래 함수를 통해서 순열을 구할수가 있다.

함수에 벡터iterator 혹은 배열의 주소를 넣으면 다음 순열(1-2-3-4의 다음 순열은 1-2-4-3) 혹은 이전 순열(1-2-4-3의 이전 순열은 1-2-3-4)의 결과가 벡터나 배열에 적용된다.

  • next_permutation: 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.
  • prev_permutation: 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 이전 순열을 구하고 true를 반환한다. 이전 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 크다면) false를 반환.


next_permutation 함수

기본 구조


// 첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

// 아래처럼 직접 비교함수를 넣어줘도 됩니다.
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);


사용법

순열을 구하고 싶은 1-2-3-4의 배열이 있다고 가정을 하면 next_permutation의 함수를 사용하면 배열의 값들이 다음 순열인1-2-4-3로 바뀌고 함수는 true를 반환합니다.


구현 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

	// 1부터 4까지 저장할 벡터 선언
	// 배열도 가능!
	vector<int> v(4);

	// 1부터 4까지 벡터에 저장
	for(int i=0; i<4; i++){
		v[i] = i+1;
	}

	// next_permutation을 통해서 다음 순열 구하기
	do{

		for(int i=0; i<4; i++){
			cout << v[i] << " ";
		}

		cout << '\n';

	}while(next_permutation(v.begin(),v.end()));

	return 0;

}


구현 결과

1 2 3 4
1 2 4 3
1 3 2 4

...

4 2 3 1
4 3 1 2
4 3 2 1


prev_permutation 함수

기본 구조


// 첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝
bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last);

// 아래처럼 직접 비교함수를 넣어줘도 됩니다.
bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);


사용법

순열을 구하고 싶은 4-3-2-1의 배열이 있다고 가정을 하면 prev_permutation의 함수를 사용하면 배열의 값들이 다음 순열인4-3-1-2로 바뀌고 함수는 true를 반환합니다.


구현 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

	// 1부터 4까지 저장할 벡터 선언
	// 배열도 가능!
	vector<int> v(4);

	// 4부터 1까지 벡터에 저장
	for(int i=0; i<4; i++){
		v[i] = 4-i;
	}

	// prev_permutation을 통해서 이전 순열 구하기
	do{

		for(int i=0; i<4; i++){
			cout << v[i] << " ";
		}

		cout << '\n';

	}while(prev_permutation(v.begin(),v.end()));

	return 0;

}


구현 결과

4 3 2 1
4 3 1 2
4 2 3 1

...

1 3 2 4
1 2 4 3
1 2 3 4


참고자료