C++ 순열(Permutation) - next_permutation

 

 

 

---

1. 순열(Permutation)

 

순열은 순서에 상관있게 값들을 나열하는 것을 의미한다.

 

 

C++ 에서는 algorithm 라이브러리의 next_permutation을 사용한다면 간단하게 구해낼 수 있다.

 

 

 

next_permutation은 인자로 반복자를 받기 때문에 vector 뿐만아니라 string 타입의 변수도 순열을 구해낼 수 있다.

 

 

 

---

2. 코 드

환경 : Visual studio 2019

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

int main() {
	string s = "1234";

	do {
		cout << s << " ";
	} while (next_permutation(s.begin(), s.end()));
	cout << "\n\n";
	


	vector<int> v = { 10, 5, 1, 2, 4 };
	int len = v.size();
	//sort(v.begin(), v.end());	// 정렬 후 next_permutation 사용해야함

	do {
		for (int i = 0; i < len; i++) {
			cout << v[i] << " ";
		}
		cout << "\n";
	} while (next_permutation(v.begin(), v.end()));

	return 0;
}

정렬X 결과

정렬O 결과

 

 

- 결과를 확인하면 하나는 일부의 순열만 구하였고, 하나는 모든 순열을 구하여서 서로 다른 것을 볼 수 있다.

 

 

이 둘의 차이는 순열을 구할 데이터의 정렬(오름차순) 유무이다. 

 

 

next_permutation은 더 큰 순열을로 재배열을 할 수 있으면 반복하여 구해내는 구조이므로 앞에 이미 큰 원소들이 배치되어 있으면 반복하지 않게 됩니다.

 

 

 

 

만약 데이터가 내림차순으로 정렬이되어 있다면 next_permutation 대신 prev_permutation을 사용하면 된다.

 

 

+) string의 경우도 마찬가지이다. 

위 예시에서는 "1234"로 이미 오름차순 정렬이 되어 있기 때문에 모든 순열을 구할 수 있었다. 

 

 

 

 

---

3. 참 조

 

next_permutation - C++ Reference

 

prev_permutation - C++ Reference