c++ next_permutation을 활용해서 조합을 뽑는 방법.

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int a[4] = { 0,0,1,1 };
	do {
		for (int i = 0; i < 4; i++)
			cout << a[i] << ' ';
		cout << '\n';

		//조합을 뽑는 경우의 코드
		/*for (int i = 0; i < 4; i++) {
			if (a[i] == 0)
				cout << i + 1<<' ';
		}
		cout << '\n';*/
	} while (next_permutation(a, a + 4));
}

위에 있는 코드는 {0,0,1,1}의 배열에서 순열을 연속적으로 출력하는 코드이다

이 코드의 출력 결과의 경우는 

이렇게 나오게 된다. 

그래서 이렇게 나오는 next_permutation을 이용해서 어떻게 {1,2,3,4} 의 배열을 이용해서 2개의 원소를 갖는 조합을 뽑는지에 대해서 생각해보자면

여기에 변경될 코드 부분이, 

//조합을 뽑는 경우의 코드
		/*for (int i = 0; i < 4; i++) {
			if (a[i] == 0)
				cout << i + 1<<' ';
		}
		cout << '\n';*/

이렇게 되는데, 이 코드를 위에 결과물과 비교해보면, 

0으로 출력된 부분들이 변경될 코드 부분에 의해서 i+1의 형태로 출력이 되고, 1로 출력된 부분들은 출력이 안되고 제외될 부분들이다. 그래서 그 과정을 손으로 작성해서 나열해보면, 

1,2

1,3

1,4

2,3

2,4

3,4

형태가 될것이고, 이게 딱 1,2,3,4중에서 2개를 뽑는 조합의 경우의 수들에 해당한다. 

만약 1,2,3,4,5중에서 2개를 중복을 뽑는 조합의 경우는 그렇다면 {0,0,0,1,1}에서 next_permutation을 돌리면서 

arr[i]==0 일때 i+1을 출력해주면 원하는 값이 나올것이다. 

이 방법을 이용해서 next_permutation을 이용해서 조합을 쉽게 구할 수 있다.

 이해는 되는 방법이지만 당장에는 바로 떠올리기 쉽지 않은 상태이다. 잘 외우도록 하자.