[C++ STL] next_permutaion

next_permutaion

 

순열과 조합 관련 문제를 풀때 C++의 next_permutaion을 사용하면 더 편리하게 해결할 수 있다.

#include<algorithm>

algorithm 헤더를 추가해줘야 한다.

next_permutation은 다음 순열이 존재하면 해당 배열을 다음 순열로 변환하고 true를 리턴 한다.

다음 순열이 존재하지 않으면 다시 첫번째 순열로 변환하고 false를 리턴한다. 

 

순열

next_permutation은 다음 순열이 존재하면 true를 리턴하고 다음순열로 변환 시켜주기 때문에 do~while문을 사용하면 쉽게 순열을 구할수 있다.

#include <iostream>
#include<algorithm>

using namespace std;

int main() {
	int a[3] = { 1,2,3 };
	do {
		for (int i = 0; i < 3; i++) {
			cout << a[i];
		}
		cout << "\n";
	} while (next_permutation(a, a + 3));
}

 

 

다음 순열이 존재하지 않으면 다시 첫번째 순열로 변환되는것을 확인해보자.

 

#include <iostream>
#include<algorithm>

using namespace std;

int main() {
	int a[3] = { 1,2,3 };
	do {
		for (int i = 0; i < 3; i++) {
			cout << a[i];
		}
		cout << "\n";
	} while (next_permutation(a, a + 3));

	cout << "다시 첫 번째 순열로 변환합니다. => ";
	for (int i = 0; i < 3; i++) {
		cout << a[i];
	}
}

 

 

다시 사전순 첫 번째 순열로 변환되는것을 확인할 수 있다.

 

정렬되지 않은 배열일 경우

#include <iostream>
#include<algorithm>

using namespace std;

int main() {
	int a[3] = { 5,1,3 };
	do {
		for (int i = 0; i < 3; i++) {
			cout << a[i];
		}
		cout << "\n";
	} while (next_permutation(a, a + 3));
}

 

정렬되지 않은 초기 순열부터 출력된다.

조합

1,2,3,4,5중에서 3개를 뽑는 경우 ( 5​C3​ )

0과1로 배열을 만들어서 0인 경우에 출력을 한다.

 

{0, 0, 0, 1, 1} => {1, 2, 3}
{0, 0, 1, 0, 1} => {1, 2, 4}
{0, 0, 1, 1, 0} => {1, 2, 5}
{0, 1, 0, 0, 1} => {1, 3, 4}

  ........                   ........

  ........                   ........

  ........                   ........

{1, 1, 0, 0, 0} => {3, 4, 5}

 

#include <iostream>
#include<algorithm>

using namespace std;

int main() {
	int a[5] = { 0,0,0,1,1 };
	do {
		for (int i = 0; i < 5; i++) {
			if (a[i] == 0)
				cout << i + 1;
		}
		cout << "\n";
	} while (next_permutation(a, a + 5));
}