재귀 알고리즘을 이용하여 순열을 출력하는 함수를 만들어보자.
입력 : n>=1개의 원소를 가진 집합
출력 : 가능한 모든 순열의 출력
ex) 입력이 {a,b,c} 라면 출력은 {(a,b,c), (a,c,d), (b,a,c), (b,c,a), (c,a,b), (c,b,a)}
- 발상
위의 예를 보면, {a,b,c}라는 입력에 대해
순열을 array에 저장해보자.
그렇다면 array[0]에 각 원소들을 한번씩 swap하고, 재귀를 이용하여 array[1]에서는 남아있는 뒤의 원소들을 한번씩 swap하면서 또다시 재귀를 하면 될 것이다. 그리고 맨 마지막 단계에서는 array전체를 출력하고 재귀를 종료하면 될 것이다. 이에 착안하여 일반화를 시켜보자.
- 일반화
permutation(i) : array[i]에 알맞은 순열의 원소를 넣는다.
array[0,…(k-1),k,…n]라는 입력이 있을 때, i=k-1에 대해 permutation이 성공하였다면,
array[0,…(k-1)]에는 이미 순열의 앞부분이 저장되어 있을 것이다. (재귀는 믿음이 중요하다.)
그렇다면 함수의 본문에서는, array[k]부분에 알맞은 순열의 원소를 넣어야 할 것이다.
permutation(array,i,size){ // array[0,...(i-1)]까지는 이미 순열이 성공적으로 저장되어 있다. array[i]를 알맞게 넣기 위한 함수
for(int j=i;j<size;j++){
swap(array[i],array[i]); // 이 명령으로 인해 array[i]까지 성공적으로 저장
permutation(i+1); //array[i+1]를 위한 재귀
swap(array[i],array[j]); // 변경하였던 array를 원위치
}
}
void permutation(char* array, int size, int i) {
//array[i]를 선정한다.
//array[0..(i-1)]는 다 각 순열에 대해 세팅되어 있다.
//array[i]를 이후의 원소와 바꾸면서 재귀로 호출한다.
//종료조건
if (i == size) {
printArray(array,size);
num++;
return;
}
for (int j = i ; j < size; j++) {
swap(array[i], array[j]);
permutation(array, size, i + 1);
swap(array[i], array[j]);
}
}
재귀 알고리즘은 수학적 귀납법으로 증명하는게 편하다.
증명하고자 하는 명제 : permutation(array,size,0)은 성공적으로 순열을 저장한다.
아래서 i는 array[i], 즉 index를 나타낸다.
Base) i=0인 경우 주어진 코드에 의해 함수는 array[0]에 각 원소를 한번씩 저장한다.
Step) i=(k-1)인 경우 permutation(array,size,(k-1))는 array[0,…(k-1)]까지 순열을 저장하고 있다 가정.
Induction) i=k인 경우 permutation(array,size,k)는 반복문에 의하여
array[k]자리에 array[k,(k+1),…(size-1)]에 있는 각 원소들을 한번씩 바꿈으로써 array[0,…(k-1),k]까지 순열을 성공적으로 저장한다.
즉, 모든 자연수 i에 대하여 permutation(array,size,i)는 성공한다.
다시말해 permutation(array,size,0)은 성공한다.
위 코드는 크기 N인 입력에 대해 depth=k인 함수의 실행마다 (N-k)개의 재귀를 호출하므로 T(N)=N!인 시간 복잡도를 가진다. 이는 N^2보다 빠른 시간이다.
코드를 오랜만에 작성해서 그런지 반복변수에 i와 j를 혼동해서 쓰고 이를 빨리 알아채지 못해서 삽질을 꽤나 오래했다. for문의 종료조건을 꼼꼼히 살펴보자.