순열

다음 순열

순열을 사전순으로 나열했을 때, 다음에 오는 순열을 어떻게 찾을것인가?

ex) 현재 3 4 1 2 라고 나열되어 있을 때 다음 순열인 3 4 2 1 을 어떻게 출력할 수 있을까

다음 순열을 찾는 알고리즘은 다음과 같다.

1. A[i-1] < A[i]를 만족하는 가장 큰 i 찾기.

2. j >= i 이면서 A[j] > A[i-1]을 만족하는 가장 큰 j를 찾는다.

3. A[i-1]과 A[j]를 swap

4. A[i]부터 순열을 뒤집는다.

코드를 작성한 후 결과를 확인해보면 다음과 같다.

#include <iostream>

using namespace std;

bool next(int *arr, int size)
{
	int x, y;
	for (int i = size - 1; i > 0; i--) {
		if (arr[i - 1] < arr[i]) {
			x = i;
			break;
		}
		else if (i == 1) return false; //마지막 순열이라면 false를 반환
	}
	for (int i = size - 1; i >= x; i--) {
		if (arr[i] > arr[x - 1]) {
			swap(arr[x - 1], arr[i]);
			break;
		}
	}
	y = size - 1;
	while (x < y) {
		swap(arr[x], arr[y]);
		x++; y--;
	}
	return true; //정상적으로 다음 순열이 나오면 true반환
}
int main()
{
	int arr[] = { 4,2,1,3 };
	int size = sizeof(arr) / sizeof(int);
	if (next(arr, size))
		for (int i = 0; i < size; i++) printf("%d ", arr[i]);
}

다음 순열이 정상적으로 출력됨을 알 수 있다.

c++ STL의 algorithm에는 이러한 기능을 구현해놓은 next_permutation이 있으며 이를 통해

편하게 이 기능을 사용할 수 있다.

---

이전 순열

이전순열 같은 경우 위의 알고리즘을 반대로 구현하면 구현할 수 있을 것이며

c++ STL의 algorithm에서 prev_permutation을 이용할 수도 있다.

https://www.acmicpc.net/problem/10972

https://www.acmicpc.net/problem/10973

다음의 문제를 통해 앞서 알아본 개념을 활용해보도록 하자.

---

모든 순열

위의 개념을 제대로 이해했다면 모든 순열을 구하는 것 또한 어렵지 않을 것이다.

https://www.acmicpc.net/problem/10974

위의 개념을 활용해 모든 수열을 출력해보는 다음 문제를 풀어보자.

풀이 소스는 다음과 같다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[8];
int main()
{
	int N;
	scanf("%d", &N);

	for (int i = 0; i < N; i++) arr[i] = i + 1;

	do {
		for (int i = 0; i < N; i++) printf("%d ", arr[i]);
		printf("\n");
	} while (next_permutation(arr, arr + N));

	return 0;
}