next_permutation 알고리즘

c++ algorithm 라이브러리에서는 next_permutation 함수를 기본적으로 제공한다.

그 기능은 일반적인 순열의 순서로 배열 등의 순서를 바꾸어주고,

순열이 최종적으로 끝나면(완전히 역순이 되면) 다시 원래 순서대로 바꾼 뒤 false를 반환해주는 함수이다.

예를 들어서

1 2 3 4 -> 1 2 4 3 -> 1 3 2 4 -> 1 3 4 2 -> ... -> 4 3 2 1 -> (false 반환) 1 2 3 4

순으로 작동한다.

또, 중복된 수가 있을 경우 제외해준다.

즉, 만약 5가 5개 있다고 치면 5!개의 결과가 나오는 것이 아니라 1개만 나온다는 것이다.

함수를 쓰다보니 함수의 시간 복잡도는 어떤지, 어떤 알고리즘으로 작동하는지가 살짝 미심쩍어서

해당 부분 함수 코드를 살펴보았고, 알고리즘이 상당히 흥미로워 메모해보기로 하였다.

g++ 라이브러리의 코드는 대게 그렇지만 알아보기 힘든 면이 있어, 정수 배열이라고 가정하고 좀 더 알아보기 쉽게 다시 써보았다.

완전히 동일한 알고리즘을 사용했으므로 동일한 결과를 낸다.

참고로 시간 복잡도는 최악의 경우 O(n)이고, 평균은 계산해봐야 알 것 같다.

#include <iostream>
using namespace std;

int arr[5] = { 1, 2, 3, 4, 4 };

bool next_permutation(int* first, int* last) {
	if (first == last) return false; // size 0
	int* i = first;
	++i;
	if (i == last) return false; // size 1
	i = last;
	--i;

	while (true) {
		int* ii = i;
		--i;
		if (*i < *ii) {
			int* j = last;
			while (*i >= *(--j));
			swap(*i, *j);
			reverse(ii, last);
			return true;
		}
		if (i == first) {
			reverse(first, last);
			return false;
		}
	}
}

int main() {
	do {
		printf("%d %d %d %d %d\n", arr[0], arr[1], arr[2], arr[3], arr[4]);
	}
	while (next_permutation(arr, arr + 5));

	return 0;
}

참고로 algorithm 라이브러리에 있는 진짜 next_permutation을 사용할 때도 위 main 함수에 적힌 대로 사용하면 된다.

알고리즘이 생각보다 재미있는데,

위 사진과 같다.

간단히 단계를 설명하면,

1) 뒤에서부터 역순이 아닌 숫자 쌍을 찾는다. 위 예시의 경우 (4, 2), (5, 4)는 역순으로 되어있으므로 넘어가고 최종적으로 (3, 5)를 찾았다. 찾은 두 원소를 앞에서부터 i, ii라 하자.

2) 이번에는 뒤에서부터 i보다 큰 j를 찾는다. 위 예시에서는 4를 찾았다.

3) i와 j를 swap

4) ii를 포함하여, 그 뒷 부분을 모두 reverse 한다.

오랜만에 정성글을 쓰니 지친다.

글 쓰다가 flash가 안되서 다시 킨다는게 실수로 글 내용을 다 날려버려서 대충 썼다.. 빨리 자야겠다.

* 190316: 설명 약간 추가