[알고리즘] next_permutation : 다음 순열

 

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