[수학] 조건, 반복문으로 순열, 중복순열, 중복조합 출력하기

1. 개념

간단한 순열과 조합은 기본적인 조건문과 반복문으로 출력할 수 있다.

N개의 숫자 중에서 M개를 뽑아 순열, 조합하는 경우를 구해보자.

 

예를 들어 1~5까지 숫자 중에서 2개를 순열, 중복순열, 조합, 중복조합으로 뽑는다고 해보자.

 

참고로,

순열은 순서의 개념이 포함되므로 모든 숫자들을 나열하는 경우이고,

조합은 순서의 개념이 없으므로 출력되는 숫자들은 오름차순, 중복조합의 경우 비내림차순이 된다.

 

2. 구현

코드로 보면 다음과 같다.

순열(P)

//순열
#include<iostream>
using namespace std;
int check[6];

int main(void) {
	//ex) P(5, 3)
	for (int i = 1; i <= 5; i++) {
		if (check[i]) continue;
		check[i] = 1;
		for (int j = 1; j <= 5; j++) {
			if (check[j])continue;
			check[j] = 1;
			for (int k = 1; k <= 5; k++) {
				if(!check[k]) cout << i << " " << j << " " << k << "\n";
			}
			check[j] = 0;
		}
		check[i] = 0;
	}
	return 0;
}

 

순열을 출력할 때에는 앞에서 사용된 숫자들을 반복사용하면 안된다. 따라서 중복을 제거하기 위하여 check[]라는 배열을 사용하여 방문체크를 해주고 그 다음의 탐색에서 방문체크가 되어있는 숫자들을 배제하였다.

---

 

중복순열(π)

//중복순열
#include<iostream>
using namespace std;

int main(void) {
	//ex) π(5, 3)
	for (int i = 1; i <= 5; i++) {;
		for (int j = 1; j <= 5; j++) {
			for (int k = 1; k <= 5; k++) {
				cout << i << " " << j << " " << k << "\n";
			}
		}
	}
	return 0;
}

 

중복해도 상관없으므로 그냥 순차적으로 반복문을 돌며 모두 탐색해주면 된다.

---

 

조합(C)

//조합
#include<iostream>
using namespace std;

int main(void) {
	//ex) C(5, 3)
	for (int i = 1; i <= 5; i++) {
		for (int j = i+1; j <= 5; j++) {
			for (int k = j + 1; k <= 5; k++) cout << i << " " << j << " " << k << "\n";
		}
	}
	return 0;
}

 

조합은 오름차순의 순서로 탐색하므로 앞의 숫자들을 탐색할 필요가 없다. 따라서 그 다음주터 다시 탐색해주면 된다.

---

 

중복조합(H)

//중복조합
#include<iostream>
using namespace std;

int main(void) {
	//ex) H(5, 3)
	for (int i = 1; i <= 5; i++) {;
		for (int j = i; j <= 5; j++) {
			for (int k = j; k <= 5; k++) {
				cout << i << " " << j << " " << k << "\n";
			}
		}
	}
	return 0;
}

 

중복조합은 비내림차순이기만 하면 된다. 즉,  다음의 탐색이 현재보다 크거나 같아야 한다.

---

 

출력 결과

각각 순열, 중복순열, 조합, 중복조합을 실행한 결과 

 

3. 정리

정리하자면 순열의 경우에만 중복을 제거하기 위하여 check라는 배열로 앞의 숫자들의 사용여부를 확인해주었다.

 

위의 경우에는 N, M이 미리 정해져 있었다. N, M이 변수일 경우 반복문을 M번 돌려야 한다. 이런 경우는 순수조건문과 반복문으로는 한계가 있다. 따라서 재귀함수라는 새로운 방법을 이용해야 한다. 이는 분할정복과 관련되어 복잡한 내용이므로 다음에서 다루었다.

[참고] 재귀함수와 반복문

https://wondrous-developer.tistory.com/10

재귀 함수와 반복문의 비교(recursion function)