2020. 1. 14. 06:24ㆍ알고리즘/수학
N개의 원소를 갖는 순열의 다음 순열을 직접 찾는 과정은 다음과 같다.
다음 순열 찾기
1.
(0 < i < N)
a[i-1] < a[i]를 만족하는 최대 i를 구한다. (조건을 만족하는 i를 구하지 못하면 해당 순열은 마지막 순열이다.)
2.
(i <= j)
a[i-1] < a[j]를 만족하는 최대 j를 구한다.
3.
a[i-1]과 a[j]의 위치를 변경한다.
4.
a[i]부터 a[N-1]까지 순서를 역으로 뒤집는다.
아래코드는 내가 직접 구현한 다음 순열을 찾는 코드이다. 해당 순열이 마지막 순열일 경우 false를 반환한다. 이외에는 다음 순열을 만들고 true를 반환한다.
bool next_perm(int *f, int* s){
int *p = 0, *q= 0;
for (int* i = f+1; i < s; ++i)
if(*(i-1) < *i) p = i;
if(!p) return false;
for (int* j = p; j < s; ++j)
if(*(p-1) < *j) q = j;
int temp = *(p-1);
*(p-1) = *q;
*q = temp;
for (int k = 0; k < (s-p+1)/2; ++k) {
temp = *(p+k);
*(p+k) = *(s-1-k);
*(s-1-k) = temp;
}
return true;
}
STL의 next_permutation과 비교하여 속도차이가 많이 날지 비교하기 위해 BOJ의 10972문제를 통해 STL의 next_permutation()을 이용한 코드와, 내가 직접만든 next_perm()을 같이 제출하였지만 둘다 채점시간 0ms로 속도차이가 나지 않았다.
아래는 추천하는 BOJ 추천 문제다.
순열이 주어지면, 이 순열이 순열의 처음부터 몇번째에 해당하는 순열인지, 혹은 숫자 N이 주어지면 N번째 순열이 무엇인지 반환 해야하는 문제다. 위에 구현한 알고리즘 혹은 STL의 next_permutation()으로 문제를 풀게되면 문제의 수행시간 기대치는 O(N!)이 된다. 그런데 N의 상한이 20이므로 해당 문제는 제한 시간 내에 풀 수 없다.
이 문제를 풀기위해서는 현재 순열이 몇번째로 계산된 순열인지 계산할 수 있는 알고리즘을 설계해야 한다. 임의의 자릿수 i(1 <= i <= N)가 주어졌을 때 1번째 자리수 부터 i번째 자리수까지 각 자리수들을 알고 있으면, 현재까지 계산된 순열의 개수를 계산할 수 있다. 내가 설계했던 알고리즘의 경우는 N개의 자릿수를 모두 계산하고, 계산할 때, 현재 자릿수가 먼저 와야할 수의 개수를 세기위해 각 자릿수에서 N개의 자릿수를 전부 탐색했다. 내가 설계했던 코드의 예상 수행시간은 O(N²)로 문제의 제한 수행시간을 만족할 수 있었다.
N개의 원소 중에서 각 자릿수가 가질 수 있는 순열의 가짓수는 (현재 자리에 올 수 있는 수의 이전 순열의 개수) * (다음 자리부터 마지막 자리 까지 만들어질 수 있는 순열의 개수) + 1이다. 예를 들어 5개의 원소로 이루어진 순열에서 3 5 X X X까지의 순열에서 현재 계산된 순열의 개수는 (3이 선택되기 전 올 수있는 순열의 개수) * (2번째 자리부터 만들어질 수 있는 순열의 개수) + (5이 선택되기 전 올 수 있는 순열의 개수) * (3번째 자리부터 만들어질 수 있는 순열의 개수) + 1로 2 * 4! + 3 * 3! + 1 = 48 + 18 + 1 = 67이다.