[C++] next_permutation 이용해서 순열 구하기

순열은 재귀함수로 구현할 수 있다. 그리 어렵진 않지만 약간 까다로운 부분도 있고 재귀함수가 어려울 수도 있다.

C++ <algorithm> 헤더에 정의되어 있는 편리한 함수인 next_permutation을 사용하면 순열을 쉽게 구할 수 있다.

(재귀를 이용한 순열 구하는 법 링크↓)

https://breakcoding.tistory.com/13

[알고리즘] 순열 (Permutation)

http://www.cplusplus.com/reference/algorithm/next_permutation/

next_permutation - C++ Reference

순열을 구할 때에는 재귀로 구하는 방법과 직접 배열의 원소를 바꿔가면서 구하는 방법이 있는데 next_permutaion 함수가 바로 두 번째 방법이다. next_permutation 함수는 배열의 원소를 직접 바꾼다.

그리고 next_permutation 함수로 순열을 구하기 전에 전제 조건은 배열 또는 벡터가 오름차순으로 정렬되어 있어야 한다.

next_permutation 함수를 호출하면 bool 타입을 리턴한다. 모든 순열을 다 구했다면 false를 리턴한다.

next_permutation 함수의 매개변수는 두 개인데 순열을 구하고 싶은 배열의 범위를 주소로 지정해주면 된다.

sort() 함수와 똑같이 [시작주소, 끝 주소) 이렇게 두 번째 인자는 열린 범위로 주면 된다.

배열이라면 next_permutation(arr, arr + 8), 벡터라면 next_permutation(v.begin(), v.end()) 이렇게 하면 된다.

 

1, 2, 3, 4를 가지고 모든 순열을 구하는 코드는 다음과 같다.

#include <iostream>
#include <algorithm>
using namespace std;


int main() {
	int arr[] = { 1, 2, 3, 4 };
	do {
		for (int i = 0; i < 4; i++) {
			cout << arr[i] << " ";
		}
		cout << endl;
	} while (next_permutation(arr, arr + 4));
	return 0;
}

위 코드의 실행 결과

이렇게 do-while문을 벗어나면 배열은 next_permutation을 호출하기 전 처음 상태가 된다.

do-while문 바깥에 이 코드를 추가해주면

cout << "다 돌고 난 뒤: ";
for (int i = 0; i < 4; i++) {
	cout << arr[i] << " ";
}
cout << endl;

호출하기 전 상태인 1 2 3 4로 다시 돌아와있는 것을 볼 수 있다.