[C++ 줍줍] next_permutation과 순열/조합

1. header

#include <algorithm>

 

2. 순열

next_permutation(v.begin(), v.end())

ex. v = {1, 2, 3, 4}
          (1) 입력 벡터가 다음 순열로 바뀌면서 true를 리턴 : v={1, 2, 4, 3}, true 리턴
          (2) 마지막 순열까지 모두 바뀌었다면 false를 리턴 : v={4, 3, 2, 1}, false 리턴
        
        따라서, (1)때문에 while문이 아닌 do-while문을 사용해야 하고 (처음 자신 포함하려고)
        (2)때문에 while문 조건문이 next_permutation이 된다.

 

void permutation() {
	int arr[] = { 1, 2, 3, 4 };

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

 

 

3. 조합

ex. v = {1, 2, 3, 4, 5}  temp = {false, false, false, true, true}

           (1) next_permutation 안에 직접 v를 넣어서 v가 다음 순열로 변하게 하지 X
           (2) v 대신 temp를 넣어서 temp의 순열을 구함
           (3) (2)에서 구한 temp 순열 케이스에서 true인 인덱스의 v값을 선택하면 조합 케이스 하나 완성!
                ex. temp = {false, true, false, false, true} 이면 조합 결과는 {2, 5}

 

void combination() {
	int arr[] = { 1, 2, 3, 4 };
	bool temp[] = { false, false, true, true };  // 조합으로 선택하려는 개수만큼 true 설정

	do {
		for (int i = 0; i < 4; i++) {
			if (temp[i] == true) {
				cout << arr[i] << " ";
			}
		}
		cout << "\n";
	} while (next_permutation(temp, temp + 4));
}