next_permutation (다음 순열 구하기)
▶ 우선 순열의 특징을 먼저 살펴봅시다!
A라는 집합의 원소가 [1, 2, 3, 4] 라고 해보자. A의 순열은 다음과 같다.
1 2 3 4 (오름차순) : 첫 순열
1 2 4 3
1 3 2 4
1 3 4 2
...
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
...
4 3 2 1 (내림차순) :마지막 순열
오름차순으로 시작했던 순열이, 최종적으로 내림차순으로 배열되어 끝나게 된다.
총 N! 개의 서로 다른 순열이 있다.
1 2 로 시작하는 순열인 1 2 ? ? 의 마지막 순열의(내림차순) 다음 순열을 어떻게 구할까?
1 2 ? ? 의 마지막 순열은 1 2 4 3(내림차순) 4 3 이 내림차순으로 끝난다.
앞에 1 2로 시작하는 마지막 순열 a가 있을것 이다. (위 에서는 1 2 4 3)
이 순열 a의 다음 순열은 앞이 1 3 으로 시작하는 첫 순열 b(오름차순)가 된다. (1 3 2 4)
여기서 핵심은 마지막 순열 다음에 오는 첫 순열은 부분은 오름차순이 된다는 것 이다.
(1 3 2 4) 에서도 2 4 는 오름차순이 된다.
▶ 다음 순열 구해보기
이제 본격적으로 다음 순열을 구해보자. 이해를 돕기 위해 7, 2, 3, 6, 5, 4, 1 과 같은 순열이 있다고 해보자.
이 순열은 7 2 3 으로 시작하는 마지막 순열이다. 어떻게 알았을까?
7, 2, 3, 6, 5, 4, 1 을 보면 6, 5, 4, 1 부분이 내림차순이다. 위 그림에서도 이를 확인할수가 있다.
1) A[i-1] < A[i]를 만족하는 가장 큰 i 찾기
그림에서 위 조건을 만족하는 i번째 값은 6이 된다.
2) j >= i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j찾기
그림에서는 4에 해당된다.
3) A[i-1] 과 A[j]의 값을 교환한다.
교환후 의 배열은 다음과 같다. [7 2 4 | 6 5 3 1]
4) A[i]부터 순열을 뒤집는다.
뒤집는 이유는 내림차순 되어있는 수를 뒤집어 오름차순으로 변경하면 7 2 4로 시작하는 첫 순열을 만들수 있기 때문이다.
결과적으로 다음 순열인 7 2 4 1 3 5 6 이 나오게 된다.
▶ 코드 구현
bool next_permutation(int *a, int n){
int i = n-1;
while(i > 0 && a[i-1] >= a[i]) i -= 1; // 1번 과정
if(i <= 0) return false;
int j = n-1;
while(a[j] <= a[i-1]) j -= 1; // 2번 과정
swap(a[i-1], a[j]); // 3번 과정
j = n-1;
while(i < j){ // 4번 과정
swap(a[i], a[j]);
i += 1;
j -= 1;
}
return true;
}
'Algorithm > PS 알고리즘 정리' 카테고리의 다른 글
[알고리즘] L-트로미노 (0) | 2022.02.10 |
---|---|
[알고리즘] 비트마스크 조합, 부분수열 (0) | 2022.01.21 |
[알고리즘] Two Pointers Algorithm : 투포인터 알고리즘 (0) | 2022.01.21 |
[알고리즘] Sweeping Algorithm : 라인 스위핑 알고리즘 (0) | 2022.01.21 |
[알고리즘] Counting inversions (0) | 2022.01.21 |
댓글