[Algorithm] 재귀함수(Recursion)를 통해 순열(Permutation) 구하기
재귀함수를 통해서 순열을 구하고 출력해보자
환경 및 선수조건
- C, C++
- 순열과 재귀함수에 대한 이해
순열이란
순열(Permutation): 순열이란 n개의 원소에서 r개를 골라서 나열하는 방법을 의미합니다.
순열의 구현 방법
- 재귀함수를 통해서 구현을 하며 아래 코드처럼 for문을 돌면서 각각 하나하나 원소에 대해서 가장 오른쪽에 있는(배열을 기준으로) 원소와 바꾸고 재귀함수를 돌려주는 식으로 해주면 됩니다.
- 아래 코드 주석에 보다 더 자세한 설명을 첨부합니다.
재귀를 통한 순열의 구현 - 1
- 아래는 모든 원소에 대해서 순열을 구할 때 즉, P(n,k)에서 n=k인 경우의 코드입니다.
permutation_example.cpp
#include <stdio.h>
int arr[] = {1,2,3,4,5};
void swap(int *a, int *b ){
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void print_arr(){
for(int i=0; i < sizeof(arr)/sizeof(int); i++)
printf("%d ", arr[i]);
printf("\n");
}
void permutation(int n, int r){
// 탈출조건으로 r이 0이 되면 순열의 한 경우가 완료되었으므로 return합니다.
if( r == 0){
print_arr();
return;
}
// 가장 끝에 있는 n-1의 위치의 원소와
// 현재 보고 있는 i의 원소를 바꿔서
// 재귀 함수에 넣어줍니다.
// 1-2-3을 예로 들으면
// 3(변수 i)과 3(변수 n-1)을 바꿉니다.
// 그러면 3은 제일 뒤에 고정이고
// 1과2를 둘이 바꾸는 경우가 생기므로
// 1-2-3과 2-1-3이 생성됩니다.
// 이제 다시
// 2(변수 i)와 3(변수 n-1)을 바꿉니다.
// 그러면 2는 제일 뒤에 고정이고
// 1과3을 둘이 바꾸는 경우가 생기므로
// 1-3-2와 3-1-2가 생성됩니다.
// 숫자가 더 커지거나해도 같은 원리로 적용됩니다.
for(int i=n-1; i>=0; i--){
swap(&arr[i], &arr[n-1]);
permutation(n-1, r-1);
// 아래처럼 다시 swap을해줘야 마지막에 모두 끝났을 때 arr가 변화없게됩니다.
swap(&arr[i], &arr[n-1]);
}
}
int main() {
permutation(sizeof(arr)/sizeof(int), sizeof(arr)/sizeof(int));
return 0;
}
재귀를 통한 순열의 구현 - 2
- 만약에 4개의 원소중에서 3개만 골라서 순열을 구하고 싶은 경우 즉, P(n,k)에서 n!=k(n>k)인 경우의 코드입니다.
- 위의 코드와 다르게 depth라는 변수를 통해서 원소의 제일 앞에서부터 하나씩 고정해나가면서 변경합니다.
permutation_example.cpp
#include <stdio.h>
int arr[] = {1,2,3,4};
void swap(int *a, int *b ){
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void print_arr(int size){
for(int i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
void permutation(int n, int r, int depth){
// r과 depth의 크기가 같아지면 출력하고 반환합니다.
// 배열 index가 0부터 depth-1까지(r-1까지)
// 즉 r개만큼 앞에서 순열이 생성되었기에 반환합니다.
if( r == depth){
print_arr(depth);
return;
}
// 원리는 위와 같습니다.
// 1-2-3에서 2개를 고른다고 가정하면
// 배열에서 1(변수 i)과 1(변수 depth)을 바꿉니다.
// 그러면 1은 제일 앞에 고정이고
// depth를 1을 증가시켜 다시 함수를 호출하면
// 2와3를 둘이 바꾸는 경우가 생기므로
// 1-2와 1-3이 생성됩니다.
// 그 다음
// 배열에서 2(변수 i)와 1(변수 depth)을 바꿉니다.
// 그러면 2는 제일 앞에 고정이고
// depth를 1을 증가시켜 다시 함수를 호출하면
// 1과3을 둘이 바꾸는 경우가 생기므로
// 2-1와 2-3이 생성됩니다.
for(int i=depth; i<n; i++){
swap(&arr[i], &arr[depth]);
permutation(n, r, depth+1);
swap(&arr[i], &arr[depth]);
}
}
int main() {
permutation(sizeof(arr)/sizeof(int), 3, 0);
return 0;
}