재귀 함수를 이용한 순열 생성 알고리즘

이번엔 1부터 n까지의 원소를 가지는 집합으로 만들 수 있는 순열들을 생성하는 알고리즘이다.

재귀 함수로 구현했기 때문에, 재귀함수 사용에 익숙하지않다면, 한 눈에 코드의 동작을 이해하기는 쉽지않을 수 있다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

#define REP(i,a,b) for(int i = a; i<=b; i++)

typedef vector<int> vi;

const int n = 4;
vi permutation;
bool chosen[n + 1];

void search() {
	if (permutation.size() == n){
		// 완성된 순열 출력
		for (int i = 0; i < permutation.size(); i++)
			cout << permutation[i] << " ";
		cout << endl;
	}
	else {
		REP(i, 1, n) {
			if (chosen[i]) continue;
			chosen[i] = true;
			permutation.push_back(i);
			search();
			chosen[i] = false;
			permutation.pop_back();
		}
	}
}

int main() {
	search();
}

 

---

만약 내장 라이브러리를 사용한다면, algorithm 표준 라이브러리에 있는 next_permutation 함수를 사용할 수 있다.

위의 코드를 아래와 같이 사용하는 것도 동일하다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>  // next_permutation 함수
using namespace std;

#define REP(i,a,b) for(int i = a; i<=b; i++)

typedef vector<int> vi;

const int n = 4;
vi permutation;

void search() {
	
	REP(i, 1, n) {
		// 벡터에 1~n까지 숫자 저장
		permutation.push_back(i); 
	}

	do {
		// 완성된 순열 출력
		for (int i = 0; i < permutation.size(); i++)
			cout << permutation[i] << " ";
		cout << endl;
	} while (next_permutation(permutation.begin(), permutation.end()));
}

int main() {
	search();
}

---

실행결과 :