순열과 조합

여러 문제들을 풀면서 경우의 수를 따질 때 모든 경우의 수를 따지기 좋은 것이

바로 순열과 조합인 걸 느끼고 정리를 해보려 한다.

 

• 중복을 포함하지 않는 순열
• 중복을 포함한 순열
• 중복을 포함하지 않는 조합
• 중복을 포함한 조합

이렇게 4가지로 나눌 수 있을 것 같다.

각각의 방법에 대해서 DFS와 c++의 algorithm 헤더 파일의 next_permutation을 사용해서 만들 수 있다.

 

 

모든 순열과 조합에 대해서 n개 중에서 m개를 뽑는 경우의 수를 보자.

 

 

• 중복을 포함하지 않는 순열(DFS)

#include <iostream>
using namespace std;
	
int ar[10], n, m;
bool vis[10];

void DFS(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) {
			cout << ar[i] << ' ';
		}
		cout << '\n';
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			vis[i] = true;
			ar[cnt] = i;
			DFS(cnt + 1);
			vis[i] = false;
		}
	}
}

int main() {
	cin >> n >> m;
	DFS(0);

	return 0;
}

 

순열과 조합은 기본적인 틀이 있는 것 같다.

cnt == m 이 되는 경우 ar 배열에 들어있는 수들을 출력해주고 아니라면

vis 배열을 통해서 중복을 체크해준다. 중복되지 않은 수라면 DFS를 한번 더 사용해서 가지치기하는 식으로 사용해주는 틀을 벗어나지 않는다.

따라서 중복을 포함하게 해주려면

 

• 중복을 포함한 순열

#include <iostream>
using namespace std;

int ar[10], n, m;

void DFS(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) {
			cout << ar[i] << ' ';
		}
		cout << '\n'; return;
	}
	for (int i = 1; i <= n; i++) {
		ar[cnt] = i;
		DFS(cnt + 1);
	}
}

int main() {
	cin >> n >> m;
	DFS(0);

	return 0;
}

 

그냥 vis 배열을 지워주면 방문을 처리하지 않으니 중복해서 뽑는다. 조심해야 할 점은 cnt == m 일 때 출력을 전부 하고 return;을 통해 종료를 해줘야 한다는 것이다. 종료하지 않으면 roof에 빠져서 탈출하지 못한다.

 

조합도 비슷하다.

 

• 중복을 포함하지 않는 조합

#include <iostream>
using namespace std;

int ar[10], n, m;
bool vis[10];

void DFS(int cnt, int idx) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) {
			cout << ar[i] << ' ';
		}
		cout << '\n'; 
	}
	for (int i = idx; i <= n; i++) {
		if (!vis[i]) {
			vis[i] = true;
			ar[cnt] = i;
			DFS(cnt + 1, i);
			vis[i] = false;
		}
	}
}

int main() {
	cin >> n >> m;
	DFS(0, 1);

	return 0;
}

 

순열과의 차이점은 idx인자를 넘겨주는 것이다 idx변수를 통해서 이전에 방문한 순열은 다시 보지 않게 처리할 수 있다.

예를 들어 1, 4와 4, 1은 수열에서 표시되지만 조합에서는 표시되지 않는다.

 

• 중복을 포함한 조합

#include <iostream>
using namespace std;

int ar[10], n, m;

void DFS(int cnt, int idx) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) {
			cout << ar[i] << ' ';
		}
		cout << '\n'; return;
	}
	for (int i = idx; i <= n; i++) {
		ar[cnt] = i;
		DFS(cnt + 1, i);
	}
}

int main() {
	cin >> n >> m;
	DFS(0, 1);

	return 0;
}

 

중복을 포함시키려면 마찬가지로 vis 배열만 지워주면 된다.