[C++] next_permutation

꿀팁을 배웠다. 순열과 조합을 사용할 때, C++에서는 next_permutation을 사용하면 된다고 한다. 

1. 순열을 이용 (예시) 1,2,3 원소 3개를 순서대로 나열하는 법 

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int arr[5] = { 1,2,3 };


	do {
		for (int i = 0; i < 3; i++) {
            cout << arr[i];
		}
		cout << '\n';
	} while (next_permutation(arr, arr + 3));
}

do while문과 next_permutation을 이용해서 순열을 표현한다. 배열이 오름차순 정렬되어있어야 한다. 

 

2. 조합 (5개의 원소 중에 3개를 뽑는 방법)

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int arr[5] = { 0,0,0,1,1 };


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

0의 개수는 뽑고자 하는 수, 1의 수는 뽑지 않는 수이다. 그렇게 기억하면 쉽다. 이것도 순열과 마찬가지로 오름차순 정렬 되어있어야 한다. i에 1을 더하면 , 1,2,3,4,5에서 뽑고자 하는 말이다. 만약 i에 n을 더한다면, [1+n,5+n]에서 뽑는다는 이야기가 된다. 

 

 

Backtracking을 할 때 유용하다고 한다. 하지만 아직 써보지는 않았다.