알고리즘 문제를 풀면서 생각보다 순열이나 조합을 구현할 일이 많다고 생각되어 정리해보았다.

순열(순서O)

1. 재귀를 이용한 순열

#include <bits/stdc++.h>
using namespace std;
int a[3]={1,2,3};
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){
	if(r==depth){
		printV(v); //종료조건
		return;
	}
	for(int i=depth; i<n; i++){
		swap(v[i],v[depth]); //바꾸기
		makePermutation(n,r,depth+1);
		swap(v[i],v[depth]); //원래로 되돌리기
	}
	return;
}
int main () {
	for(int i=0; i<3; i++){
		v.push_back(a[i]);
	}
	makePermutation(3,3,0);
	return 0;
}

결과

123
132
213
231
321
312

2. next_permutation 과 prev_permutation 함수 사용

c++에서는 next_permutation 함수와 prev_permutation 함수를 제공하는데,

각각 “오름차순인 배열” 인 경우, “내림차순” 인 경우 순열을 제공한다.

#include <bits/stdc++.h>
using namespace std;
void printV(vector<int> &v){
	for(int i=0; i<v.size(); i++){
		cout<<v[i]<<" ";
	}
	cout<<'\n';
}
int main () {
	int a[3]={1,2,3};
	vector<int> v;
	for(int i=0; i<3; i++){
		v.push_back(a[i]);
	}
	do{
		printV(v);
	}while(next_permutation(v.begin(),v.end()));
	cout<<"---------------------\n";
	v.clear();
	for(int i=2; i>=0; i--){
		v.push_back(a[i]);
	}
	do{
		printV(v);
	}while(prev_permutation(v.begin(),v.end()));

	return 0;
}
결과

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
---------------------
3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3

조합(순서X)

1.재귀를 이용한 조합

#include <bits/stdc++.h>
using namespace std;
int n=5, k=3, a[5]={1,2,3,4,5};
void print(vector<int> b){
	for(int i:b) cout<< i << " ";
	cout<<'\n';
}
void combi(int start, vector<int> b){
	if(b.size()==k){
		print(b);
		return;
	}
	for(int i= start+1; i<n; i++){
		b.push_back(i);
		combi(i,b);
		b.pop_back();
	}
	return;
}
int main () {
	vector<int> b;
	combi(-1,b); //i가 0부터 시작하기때문에
	return 0;
}

답

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

2. 중첩 for문을 이용한 조합

#include <bits/stdc++.h>
using namespace std;
int n=5, a[5]={1,2,3,4,5}; 
int main () {
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			for(int k=j+1; k<n; k++){
				cout<<i<<" "<<j<<" "<<k<<'\n';
			}
		}
	}
	return 0;
}

답

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