순열과 조합 구현하기

1. 순열

서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 것
순열은 next_permutation(오름차순), prev_permutation(내림차순) 함수 사용하여 만들 수 있다.
매개변수로는 순열을 시작할 범위의 첫 번째 주소, 포함되지 않는 마지막 주소를 넣어서 함수를 실행하면 모든 원소에 대한 순열이 만들어진다.
이 두 함수를 사용하려면 사용 전에 무조건 벡터가 정렬되어 있어야 한다는 주의사항이 있다.

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()));
}

그러나 이 함수는 기본적으로, nPn 값을 반환한다. nPr 순열을 구하는 방법은 다음과 같다.

int main(){
	int a[3] = {1, 2, 3};
	vector<int> v;
	for(int i = 0; i < 3; i++)v.push_back(a[i]);

	int n = 3;
	int r = 2;
    
	do{
		printV(v);	
		reverse(v.begin() + r, v.end());
	}while(next_permutation(v.begin(), v.end()));
}

만약 reverse를 해주지 않고 r=2 부분까지 출력을 한다고 가정하면, {1, 2, 3, 4, 5} 다음 순열은 {1, 2, 3, 5, 4} 이기 때문에 1, 2의 출력이 반복된다. 그러나 {1, 2, 3, 4, 5}에서 r=2 뒷 부분을 뒤집어 주면 {1, 2, 5, 4, 3}이 되고, 이러면 그 다음 순열은 바로 {1, 3, 2, 4, 5}가 되기 때문에 1, 3을 출력하는 부분으로 즉시 넘어간다.
따라서 reverse(v.begin() + r, v.end())로 nPr 순열을 만들 수 있다.

---

2. 조합
서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관없이 선택하는 것

void combi(int start, vector<int> b){
	if(b.size() == k) return;
    
    for(int i = start + 1, i<n; i++){
    	b.push_back(i);
        combi(i, b);
        b.pop_back(i);
    }
}