[Algorithm] 순열 : 재귀함수로 만드는 순열

🎈 코드 예시

#include <bits/stdc++.h>

using namespace std;

vector<int> v;
void printV(vector<int> &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << " ";
    }
    cout << "\n";
}

void makePermutation(int n, int r, int depth)
{
    // n개 중 r개를 뽑는 순열
    cout << n << " : " << r << " : " << depth << "\n";
    if(r == depth)
    {
        printV(v);
        return;
    }
    // depth를 기반으로 swap
    for (int i = depth; i < n; i++)
    {
        swap(v[i], v[depth]);
        makePermutation(n, r, depth + 1);
        swap(v[i], v[depth]);
    }
}
int main()
{
    for (int i = 1; i <= 3; i++)
        v.push_back(i);
    makePermutation(3, 3, 0);
    return 0;
}

 

• 매개변수:
  • n: 입력 데이터의 크기 (벡터 v의 길이)
  • r: 선택할 개수 (여기서는 3개)
  • depth: 현재 생성 중인 순열의 깊이 (재귀 깊이)
• 작동 원리:
  1. 종료 조건:
     • r == depth: 선택할 개수만큼 선택한 경우(현재 순열 완성) printV(v)를 호출하여 순열을 출력하고 종료
  2. 재귀 호출:
     • 반복문으로 현재 depth부터 n까지 순회하며 swap을 사용하여 요소의 순서를 변경
     • 순열을 하나씩 생성한 뒤, 다시 원래 순서를 복원(백트래킹).
     • swap을 두 번 해주는 이유
       • ex) {1,2,3}에서 swap하여 새로운 순열 {1,3,2}를 생성하고 makePermutation을 하고 또 다른 순열을 만들기 위해서는 다시 {1,2,3}으로 원상복귀(swap을 한번더 해줌)해야한다.
       • 재귀 호출(makePermutation)이 종료된 직후에 복원 작업이 실행된다.

 

코드에서 첫 번째 swap을 호출하면, 순열을 만드는 과정에서 벡터 v의 요소들이 교체된다. makePermutation 함수가 재귀적으로 호출되면서 swap은 각 단계에서 depth를 기준으로 이루어진다.

벡터 v는 처음에 {1, 2, 3}으로 초기화된 상태.

호출 순서 요약 (벡터 v = {1, 2, 3} 기준):

1. makePermutation(3, 3, 0)
   • swap(v[0], v[0]) → 그대로 {1, 2, 3}.
   • makePermutation(3, 3, 1) 호출.
2. makePermutation(3, 3, 1)
   • swap(v[1], v[1]) → 그대로 {1, 2, 3}.
   • makePermutation(3, 3, 2) 호출.
3. makePermutation(3, 3, 2)
   • swap(v[2], v[2]) → 그대로 {1, 2, 3}.
   • makePermutation(3, 3, 3) 호출.
4. makePermutation(3, 3, 3)
   • 조건 만족 → printV(v) → 출력: 1 2 3.
   • 재귀 종료 → 이전 호출(makePermutation(3, 3, 2))로 복귀.
5. makePermutation(3, 3, 2) 복귀
   • swap(v[2], v[2]) 복원 → {1, 2, 3} 그대로.
   • for 루프 종료 → 이전 호출(makePermutation(3, 3, 1))로 복귀.
6. makePermutation(3, 3, 1) 복귀
   • 다음 swap 실행: swap(v[1], v[2]) → 벡터가 {1, 3, 2}로 변경.
   • 이후 makePermutation(3, 3, 2) 호출.

---

전체 순열 탐색 순서 출력

아래는 swap에 따라 생성되는 순열과 그 과정:

1. {1, 2, 3}
2. {1, 3, 2}
3. {2, 1, 3}
4. {2, 3, 1}
5. {3, 2, 1}
6. {3, 1, 2}

swap에 의해 매 순간 v의 상태가 바뀌면서 위 순열들이 출력된다.