출처 : http://hochulshin.com/permutation-composition-summary/
순열, 중복 순열, 조합, 중복 조합에 대한 이해를 해보자.
1. 개요
순열, 중복 순열, 조합, 중복 조합를 비교해 보자.
1.1 순열
- 중복없이 n개 중에서 r개를 뽑아 순서를 정해 나열하는 경우를 말한다.
- 예를 들어, 다섯 개의 문자 a, b, c, d, e를 일렬로 배열해야 하는 것을 생각해보자.
a, b, c, d, e
a, b, c, e, d
a, b, e, c, d
...
1.2 중복 순열:
- n개 중에서 r개를 뽑아 순서를 정해 나열하는 경우, 같은 것(종류)을 다시 뽑을 수 있는 것을 말한다.
- 예를 들어, 숫자 1,2,3을 이용해 만들수 있는 3자리 정수를 모두 구해야 한다고 생각해 보자.
111
112
113
121
122
...
1.3 조합
- 중복없이 n개 중에서 r개를 순서에 상관없이 뽑는 것을 말한다.
- 예를 들어 시간이 서로 다른 4 과목 A, B, C, D중 2개 만을 선택해서 수강 신청 하는 경우를 생각해보자.
AB
AC
AD
BC
BD
CD
1.4 중복 조합
- n개 중에서 r개를 같은 것(종류)를 뽑을 수 있으며 뽑히는 순서에 상관없이 선택하는 것을 말한다.
- 예를 들어 1인당 2개의 표를 가지고 4개의 연예인(A, B, C, D)에게 선호도 투표를 하는 경우를 생각해보자. 이때 2개의 표를 같은 인물에게 2표를 모두 행사할 수 있다면.
AA
AB
AC
AD
BB
BC
BD
..
2. 순열
2.1 개요
세개의 문자 a,b,c 중 2개를 택해 일렬로 배열하는 방법의 수는 첫 번째 자리의 문자를 택하는 가짓수(3)와 남은 문자 중에서 두번째 자리에 놓을 가짓수(2)를 곱한 것과 같다. 이처럼 서로 다른 n가지에서 r가지를 택하는 순열의 모든 경우의 수는 nPr로 표시할 수 있다.
nPr = n!/(n-r)!, nP0는 1, nPn은 1(모두 선택하거나, 아무것도 선택하지 않을 경우의 수는 1)
2.2 구현
nPr을 이루는 각 경우를 뽑아내기 위한 구현의 예제는 다음과 같다.
- 문제: 1, 2, 3, 4 숫자 4개가 주어졌을때 이 중 3개의 숫자를 뽑아 한번씩만 사용해서 만들 수 있는 모든 숫자를 출력하라.
#include <stdio.h>
int T[10]; //nPr을 이루는 각각의 경우를 저장
int data[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
void swap(int *i, int *j){
int temp = *i;
*i = *j;
*j = temp;
}
/*T[]에서 q개 출력*/
void process(int q){
for(int i = q-1; i>= 0; i--){
printf("%d ", T[i]);
}
printf("\n");
}
/*data[]에서 앞에서부터 n개의 숫자 중 r개를 선택해서 순열을 출력하는 함수. q는 출력 시 출력 갯수 지정*/
void Perm(int n, int r, int q){
if(r == 0){
process(q);
return;
}
for(int i = n-1; i>=0; i--){
swap(&data[i], &data[n-1]); //n-1을 모든 index와 swap해서 다양한 순서를 만든다.
T[r-1] = data[n-1]; //T의 뒤에서부터 결과값 저장
Perm(n-1, r-1, q); //다음 index로 진행
swap(&data[i], &data[n-1]);
}
}
int main(void){
Perm(4, 3, 3);
return 0;
}3. 중복 순열
3.1 개요
서로 다른 n개의 중복을 허용하여 r개를 택하여 나열하는 방법을 n개에서 r개를 택하는 중복 순열이라고 한다. 중복 순열의 모든 경우의 수는 아래와 같다.
중복 순열 nㅠr = n의 r제곱승
3.2 구현
중복 순열의 각 경우를 출력하는 코드를 순열 구현 코드와 비교하면서 확인해보자. 1, 2, 3, 4 숫자 4개가 주어지고 이 중 3개를 뽑는데 같은 숫자가 반복되어도 가능하다.
#include <stdio.h>
int T[10]; //nPr을 이루는 각각의 경우를 저장
int data[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
void swap(int *i, int *j){
int temp = *i;
*i = *j;
*j = temp;
}
void process(int q){
for(int i = q-1; i>= 0; i--){
printf("%d ", T[i]);
}
printf("\n");
}
/*data[]에서 앞에서부터 n개의 숫자 중 r개를 (중복) 선택해서 순열을 출력하는 함수. q는 출력 시 출력 갯수 지정*/
void PI(int n, int r, int q){
if(r == 0){
process(q);
return;
}
for(int i = n-1; i>=0; i--){
swap(&data[i], &data[n-1]);
T[r-1] = data[n-1];
PI(n, r-1, q); //유일하게 다른 부분. 1가지를 선택한 후 선택할 수 있는 종류를 줄이지 않음.(n)
swap(&data[i], &data[n-1]);
}
}
int main(void){
PI(4, 3, 3);
return 0;
}4.조합
4.1 개요
서로 다른 n개에서 순서를 생각하지 않고 r개(0<=r<=n)를 택하는 것을 조합이라고 한다. n개 중 r개를 선택하는 모든 조합의 경우의 수는 다음과 같다.
nCr = nPr을 r!로 나눈 것 = n!/(r!*(n-r)!), nC0과 nCn은 1이다.
nCr은 다음과 같은 관계를 가진다.
nCr = n-1Cr-1 + n-1Cr
참고로, 서로 다른 n개의 물건을 p개, q개, r개의 3개의 그룹으로 나누는 방법은 다음과 같다.
nCp * n-pCq * rCr
예를 들어, 서로 다른 종류의 꽃 15송이를 다섯 송이씩 세묶음으로 나누는 방법의 수는 15C10 * 10C5 * 5C5이다.
4.2 구현
조합을 한 각 경우를 출력하는 것을 생각해보자. nCr = n-1Cr-1 + n-1Cr, nC0 = 1 관계를 이용한다. 1, 2, 3, 4 숫자 4개가 주어졌을때 순서 상관없이 3개씩 묶어 그룹을 만들 때 그 멤버를 출력한다.
#include <stdio.h>
int T[10]; //nPr을 이루는 각각의 경우를 저장
int data[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
void process(int q){
for(int i = q-1; i>= 0; i--){
printf("%d ", T[i]);
}
printf("\n");
}
/*data[]에서 앞에서부터 n개의 숫자 중 r개를 선택해서 조합을 출력하는 함수. q는 출력 시 출력 갯수 지정*/
void Comb(int n, int r, int q){
if(r == 0){
process(q);
return;
}else if(n<r){
return;
}
else { //loop이 아님
T[r-1] = data[n-1];
Comb(n-1, r-1, q); //n-1Cr-1: 현재 아이템을 선택한 경우
Comb(n-1, r, q); //n-1Cr: 현재 아이템을 선택하지 않은 경우
}
}
int main(void){
Comb(4, 3, 3);
return 0;
}5. 중복 조합
5.1 개요
서로 다른 n개에서 순서를 생각하지 않고 중복을 허용하여 r개(0<=r<=n)를 택하는 것을 중복 조합이라고 한다. 예를 들어, 숫자 1, 2에서 중복을 허용하여 3개를 선택하는 조합은 (1,1,1)(1,1,2)(1,2,2)(2,2,2)이다. 중복 조합의 모든 경우의 수는 다음과 같이 표현된다.
nHr = n+r-1Cr
nHr은 다음과 같은 관계를 가진다.
nHr = nHr-1 + n-1Hr
5.2 구현
여기서 중복 조합의 구현은 생략한다. 스스로 구현해 보자!
'알고리즘' 카테고리의 다른 글
| DFS,BFS (0) | 2015.07.09 |
|---|---|
| XOR (0) | 2015.06.12 |
| KMP 알고리즘 (문자열 패턴 검색) (0) | 2015.05.29 |
| [알고리즘] 퀵 정렬(Quick Sort) (0) | 2014.12.01 |
kuku_dass
main.cpp
input_test.txt