C++ 순열(permutation)과 조합(combination)

순열(Permutation)이란?

순서가 정해진 임의의 집합을 다른 순서로 섞는 연산

 

ex) n개의 집합 중 n 개를 골라라

 

수학 공식 ) nPr = n! / (n-r)!

 

 

순열 구현하기

1. next_permutation / prev_permutation

next_permutation : 오름차순 배열 기반

prev_permutation : 내림차순 배열 기반

 

next_permutation([first, last))

- first : 순열을 시작할 범위의 첫번째 주소

- last : 포함되지 않은 마지막 주소

 

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


void printV(vector<int> &v) {
	for(int i = 0; i < v.size(); i++) {
		cout << v[i] << ' ';
	}
	cout << '\n';
}

...


for (int i = 1; i <= 3; i++) {
	v.push_back(i);
}

do {
	printV(v);
} while(next_permutation(v.begin(), v.end()));

 

만약 배열의 특정 부분만 이용해서 순열을 구하고 싶다면?

- next_permutation(v.begin(), v.begin() + 3);

 

 

주의할점 !!)

- prev 는 내림차순 정렬하여,

- next 는 오름차순 정렬하여 사용해야 함!

 

 

2. 재귀함수를 이용한 순열

void makePermutation (int n, int r, int depth) {
	cout << n << " : " << r << " : " << depth << "\n";
	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;
}

 

주의할점 !!) 재귀함수는 종료 조건이 필요하다

 

 

 

 

 

 

조합(Permutation)이란?

순서 상관없이 다른 순서로 섞는 연산

 

수학 공식 ) nCr = n! / [r! * (n-r)!]

 

조합 구현하기

1. 재귀함수를 이용한 조합

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

 

 

 

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

3개 이상 뽑는 경우에는 중첩 for 문 보다 재귀함수를 이용하자 

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 << '\n';
		}
	}
}

 

 

 

조합 특징!)

nCr = nC(n-r) 은 동일하다

ex) 9개 중 2개 뽑는 방법과 9개 중 7개 뽑는 방법이 동일

즉, 9개 중 7개 뽑는 문제 나오면 -> 9개 중 2개 뽑아서 제거하면 된다