[알고리즘/C++] 재귀함수로 순열 구현하기

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;
vector<int> v{ 1,2,3 };

void printV(vector<int> &v) {
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << "\n";
	return;
}
void Permutation(int n, int r, int depth) {
	cout << n << ":" << r << ":" << depth << endl;
	if (r == depth) {
		printV(v);
	}

	for (int i = depth; i < n; i++) {
		swap(v[depth], v[i]);
		Permutation(n, r, depth + 1);
		swap(v[depth],v[i]);
	}
	cout << '\n';
	return;
}
int main() {
	Permutation(3, 3, 0);
	return 0;
}

 

재귀함수로 순열을 구현하는데 swap함수가 주로 쓰인다.

for문 안의 로직을 간단히 살펴보자면,

벡터나 배열의 두 수를 스왑하고,

재귀호출을 한 후

다시 두 수를 스왑해서 원상복귀 시킨다.

 

for문을 통해 depth에서 i가 1씩 늘어나고 swap이 되면 재귀호출이 된다.

결국엔 제일 끝에 있는 두 요소가 swap이 되면,

재귀 호출 시 기저사례에 걸리게 되어 순열 하나를 출력하고,

가장 최근에 했던 swap의 이전 상태로 원상복귀가 된다.