순열 알고리즘 구현

순열 알고리즘

• 순열 알고리즘을 직접 구현하기 위해서는 어릴적 수형도를 그릴때를 생각하면 조금 쉽다.
• {'A','B','C'} 이렇게 A , B, C라는 3개의 데이터가 있을때 가장 첫 번째 올 수 있는 경우는 'A'가 첫 번째 오는 경우 'B'가 첫 번째 오는 경우 ' 'C'가 첫번째 오는 경우'
• 세가지 시작값을 정하는 초기 경우를 for문으로 구현하고 나머지 배열은 이렇게 세가지 경우로 부터 각각 재귀적으로 다음 단계를 수행하면 된다.

코드

#include <stdio.h>

char copy[] = {'A','B','C'};

void permutaion(char arr[], int start, int end);
void printArray(char arr[], int size);
void swap(char arr[], int a, int b);


int main(){
    int size = sizeof(copy)/sizeof(char);

    printf("fist value:\n");
    printArray(copy,size);

    printf("start:\n");

    permutaion(copy,0,size-1);

    return 0;
}

void permutaion(char arr[], int start, int end){
    if(start == end+1){
       printArray(arr,end+1);
    }

    for(int i = start; i<=end;++i){
        swap(arr,start,i);
        permutaion(arr,start+1,end);
        swap(arr,start,i);
    }
}

void printArray(char arr[], int size){
        for(int i = 0;i<size;++i){
            printf("%c ",copy[i]);
        }
        printf("\n\n");
}

void swap(char arr[], int a, int b){
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

알고리즘 수행 단계

• permutation에서 end값은 변하지 않고 변하는 값은 start값과 for문의 i이다.
• 재귀함수의 반환 조건은 순열의 데이터를 저장한 배열의 길이보다 길어졌을 경우(제일 아래 깊이 만큼 탐색한 상태) 리턴을 하고, 중간에 있는 함수들은 i가 end만큼 반복 했을때 리턴한다. 리턴 직전에는 현재 스택에서 swap을 한 상태를 다시 원래 상태로 돌려주고 리턴을 하거나 i값이 증가해야 다음 단계를 다시 반복, 재귀적으로 수행가능하도록 한다.
• 내가 호출한 함수에서 수행을 마치고 돌아올 경우 원래상태로 나의 스택 범위에서 swap한 데이터를 다시 swap하여 나의 스택 시작 상태로 데이터를 만들고 i값을 증가하여 다음을 수행한다.
• 아래 그림에서는 permutation이 호출 되는 경우를 트리형태로 표현했고,괄호속 인자는 변하는값 start와 i를 적어주었다.