[algorithm] 순열과 조합

next_permutation

현재 나와있는 수열에서 다음 순열을 구하고 true를 반환. 다음 순열이 없다면 false를 반환.

 

prev_permutation

현재 나와있는 수열에서 이전 순열을 구하고 true를 반환. 이전 순열이 없다면 false를 반환.

 

배열의 경우 시작인덱스와 끝 인덱스, 벡터의 경우 iterator를 인자로 넘겨주면 된다.

 

순열을 구하는 코드

 

	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));

	/*
	123
	132
	213
	231
	312
	321
	*/

 

조합을 구하는 코드

 

// 4개의 수 중에서 2개를 순서없이 뽑는 조합
// n개의 수 중에서 m개의 수로 조합을 뽑는 경우라면 원소의 개수를 n, 0을 m개만큼 넣어두면 된다
int a[4] = { 0, 0, 1, 1 };

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

	/*
	12
	13
	14
	23
	24
	34
	*/