순열
next_permutation 함수는 <algorithm> header에 정의된 함수로, [first, last)를 다음(next) 순열로 치환한다.
(last는 범위에 포함되지 않음.)
다음 순열, 즉 "next permutation"이 존재하면 true를 반환하고,
아니면 첫 번째 순열로 바꾸어 false를 반환한다.
이러한 성질 때문에, 주로 do while문과 함께 쓰이며,
모든 순열을 탐색하고 싶다면 next_permutation에 배열을 넣기 전에 오름차순으로 정렬을 해야 한다.
예를 들어, int arr[4]={3,2,4,5};라는 배열이 있다고 하자.
do{
for(int i=0;i<4;i++)
cout<<arr[i]<<' ';
cout<<'\n';
}while(next_permutation(arr, arr+4));이 코드를 실행했을 때, 출력은 어떻게 될까?
<정답>
| 3 2 4 5 3 2 5 4 3 4 2 5 3 4 5 2 3 5 2 4 3 5 4 2 4 2 3 5 4 2 5 3 4 3 2 5 4 3 5 2 4 5 2 3 4 5 3 2 5 2 3 4 5 2 4 3 5 3 2 4 5 3 4 2 5 4 2 3 5 4 3 2 |
정답을 맞췄다면 next_permutation의 기본 원리를 이해한 것이다.
(맨 처음에 3 2 4 5가 출력되는 이유는 do while문은 처음에 조건문 확인을 하지 않기 때문이다.)
조합
next_permutation으로 순열뿐만 아니라 조합도 구현할 수 있다.
다시 int arr[4]={1,2,3,4}; 배열에서 element 2개를 뽑아야 한다고 가정해보자.
4개 중에 2개를 뽑는 조합 문제다.
이럴 때는 뽑아야 하는 element를 0으로 표시한 또 다른 배열 int tmp={0,0,1,1};을 이용한다.
int arr={1,2,3,4};
int tmp={0,0,1,1};
do{
for(int i=0;i<4;i++){
if(tmp[i]==1) continue;
cout<<arr[i]<<' ';
}
cout<<'\n';
} while(next_permutation(tmp, tmp+4));여기서 주목할 것은 next_permutation의 parameter로 arr이 아니라 tmp가 들어가야 한다는 것이다.
왜냐하면 tmp[i]의 0이 arr[i]를 조합에 포함시킬지 말지를 결정하기 때문이다.
그렇다면 뽑아야 하는 element를 1이 아닌 0으로 표시했을까?
조합을 오름차순 순서대로 구하기 위함이다.
<참고>cpp reference: https://en.cppreference.com/w/cpp/algorithm/next_permutation
