[Algorithm] 순열 구하기

재귀함수를 이용하여 순열을 구하는 알고리즘이다. 

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

vector<int> permutation;

void search(int n, bool chosen[]) {
	vector<int>::iterator it;
	if (permutation.size() == n) {
		for (it = permutation.begin(); it != permutation.end(); it++) {
			cout << *it << " ";
		}
		cout << "\n";
	}

permutation 벡터가 가득 하면 담겨있는 원소를 모두 출력한다. 

	else {
		for (int i = 1; i <= n; i++) {
			if (chosen[i]) {
				continue;
			}
			permutation.push_back(i);
			chosen[i] = true;
			search(n, chosen);
			permutation.pop_back();
			chosen[i] = false;
		}
	}
}

아직 가득차지 않았다면 for문을 순회하면서 i번째 원소를 담느냐 담지 않느냐의 분기 가운데에 

 

search 함수를 재귀호출한다. search 함수는 for문을 재순회하면서 아직 담기지 않은 원소를 담을지 안 담을지 또 다시 선택한다. 

 

결국 permutation이 가득 찰 때까지 재귀함수 호출은 반복되고 모든 경우의 수의 순열이 구해진다. 

 

int main() {
	bool chosen[5] = { false };
	search(sizeof(chosen)-1, chosen);
}

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1