[코드 리뷰] 순열 생성 알고리즘

# 처음 작성했던 코드

void permutation(vector<char>& array)
{
    for(int i=0;array.size();i++)
    {
        if(array.size()<=1)
        {
            cout<<array[0]<<endl;
        }
        else
        {
            swap(array[0],array[i]);
            cout<<array[0]<<" ";
            vector<char> array_new;

            for(int j=1;j<array.size();j++)
                array_new.push_back(array[j]);
            permutation(array_new);
            swap(array[0],array[i]);

        }
       
    }
}

 

구현 개요

* 배열의 첫번째 원소를 고정한 후 나머지 배열에 대해 재귀적으로 순열을 생성하는 방식입니다.

* 종료 조건과 재귀 호출을 통해 남은 요소들로 모든 가능한 순열을 출력하는 구조로 작성되었습니다.

 

당시의 생각)

1) 동작 개념은 잡혀있었음.

 - 배열의 첫 원소를 고정시키고 나머지 배열을 작업하는것.

 

2) 종료 조건 또한 생각하고 있었음.

 - 반복시키는 배열의 수가 1보다 작을 때 종료조건.

 

문제점

 

1. 종료 조건의 위치 문제

 * 재귀 함수 호출시 종료조건은 가장 먼저 확인되어야 합니다. 배열의 크기가 1 이하일때 바로 종료하지 않고 반복문을 수행하게 되어 무한루프에 빠지게 되었습니다.

 

2. 최종 출력 형식 문제

 * 최종 출력 형식은 순열과 같이 1,2,3,4 / 1,2,4,3 으로 출력되도록 요청되었습니다.

   이에 따라, 모든 원소의 배치가 완료된 이후에 출력되도록 구현해야 합니다.

 

# 최종 변경 코드 

void permituation(vector<int>& array,int left)
{
    if(left<=1)
    {
        print_all(array);
        return;
    }

    for(int i= array.size()-left;i<array.size();i++)
    {
        swap(array[array.size()-left],array[i]);
        permituation(array,left-1);
        swap(array[array.size()-left],array[i]);
    }

}