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

✔️ 순열은 swap의 과정이 있어야함

✔️ make_permutation만 기억해도 되지만 기억 안날 때를 대비해 재귀함수로 만드는 법도 기억하기!

 

💻 순열을 코드로 구현 (재귀함수 사용)

#include<bits/stdc++.h>
using namespace std;

int a[3]={1,2,3};
vector<int> b;

void printV(vector<int> &b){
    for(int i=0;i<b.size();i++){
	    cout<<b[i]<"\n";
    }
    cout<<"\n";
}
void makePermutation(int n,int r, int depth){
    if(r==depth){
	    printV(b);
	    return;
    }
	
    for(int i=depth;i<n;i++){
	    swap(b[i],b[depth]);
	    makePermutation(n,r,depth+1);
	    swap(b[i],b[depth]);//원복을 하는 과정
    }
}

int main(){
    for(int i=0;i<3;i++)b.push_back(a[i]);
    makePermutation(3,3,0);
    return 0;
}

>>123
  132
  213
  231
  321
  312

makePermutation 함수에서 depth가 뽑는 갯수 만큼이 되면 출력 될 수 있도록 하고

swap의 과정을 통해 순열 결과를 도출해낼 수 있게함

for(int i=depth;i<n;i++){
     swap(b[i],b[depth]);
     makePermutation(n,r,depth+1);
     swap(b[i],b[depth]); //원복을 하는 과정
}

- 원복이란 ?

= 123 -> 132 (123을 132로 바꾼 뒤에 다시 123으로 원복을 해야 다시 바꿀 수 있음)

ex) 123 -> 132 -> 123 -> 213 (원복 후 다시 변경)

 

(코드 도식화)

도식화를 2번정도 해보며 함수의 흐름을 파악하는 것이 중요!