[C++ STL] 순열 (next_permutation, prev_permutation)

순열 (permutation) 이란 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 것을 말한다.

 

DFS 등 다른 알고리즘을 통해 구현을 할 수도 있지만, C++ STL에서는 함수를 제공하고 있다. next_permutation(오름차순)과 prev_permutation(내림차순)이 있으며, 오름차순, 내림차순의 기준은 사전적(lexicographically)순서 입니다. 인자로는 vector, array, string등 요소 값을 갖는 자료형이 될 수 있다. 만약 다음 순열이 존재하면 true를 return 하고, 다음 순열이 존재하지 않는 경우, 첫번째 순열로 재배치 되고 false를 return 한다.

 

bool next_permutation( BidirIt first, BidirIt last );

bool next_permutation( BidirIt first, BidirIt last, Compare comp );

 

 

Definition

<algorithm>

 

Parameter

first, last, comp : permutation 범위와 compare 함수를 지정할 수 있다. 

 

 

<사용예 1 - 4자리 숫자의 순열 표시>

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

using namespace std;

int main() {

	vector<int> f(4);
	vector<int> b(4);

	for (int i = 0; i < 4; i++) {
		f[i] = i + 1;
	}

	for (int i = 0; i < 4; i++) {
		b[i] = 4 - i;
	}

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

		cout << '\n';

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

	cout << "********************************\n";

	do {

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

		cout << '\n';

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

	return 0;
}

 

출력

 

<사용예2 - 문자열>

#include <algorithm>
#include <string>
#include <iostream>

using namespace std;

int main()
{
    string s = "aba";
    sort(s.begin(), s.end());
    do {
        cout << s << '\n';
    } while (next_permutation(s.begin(), s.end()));
}

출력