먼저 순열(permutation)과 조합(combination)에 대해 알아보자
순열 : 서로다른 n개 중 r개를 택하여 순서대로 나열하는 방법의 수 (표시 : nPr)
n (n-1) (n-2) ..... (n-r+1) : 10P3 이면 10x9x8 즉 10! / 7! 이 되고,
12P5 이면 12x11x10x9x8 즉 12! / 7! 이 된다.
위 식에서 분자와 분모에 (n-r)!을 곱해주면
n!
nPr = (n-r)! 이 된다.
중복순열 : 서로다른 n개 중 중복을 허용하여 r개를 선택해 순서대로 나열하는 방법의 수(표시 : n∏r )
중복을 허용하므로, 각각의 선택에 대한 확률은 n이 된다.
즉 n^r (n의 r승)
조합 : 서로다른 n개 중 중복을 허용하여 r개를 선택하는것. (표시 : nCr)
순열과 비교했을때, 순서가 없는 것이 조합이다.
즉, {a, b, c}에서 2개를 선택한다고 할때
nPr = {ab, ac, bc, ba, ca, cb} 총 여섯개이지만,
nCr = {ab, ac, bc} 이렇게 세가지가 된다.
r개를 선택하는 순열에서 순서를 무시하게 되면,
서로 같은 조합은 r!개가 나온다.
그러므로
n!
nCr = nPr / r! = r!(n-r)! 이 된다.
자 이제 본격적으로 C언어와 만나보도록 하자
위의 공식대로 계산할 경우 n의 값이 커짐에 따라서
n! 이 크게 늘어나 오버플로우(overflow)를 유발한다.
n=13 일 때, 13! = 6,227,020,800 . (4byte unsigned int 형의 최대값은 4,294,967,296)
자 이제, nCr을 점화식을 이용하여 표현해 보면.
n-r+1
nCr = r nCr-1 ( n>0 )
nCr = 1 ( n=0 ) 와 같이 나타낼 수 있다.
자 드디어 프로그래밍이다.
재귀함수를 이용하여 간단하게 nCr을 표현해보자.
long combi(int n, int r){
if(n<0 || r<0){ // 이 부분은 main 함수 내에서 처리하게되면,
printf(" n과 r은 양의 정수이어야 합니다"); // 실제로 꼭 필요한 부분은 아니지만,
break; // 예외를 생각하면서 코딩을 하는게
} // 좋을거라 생각한다.
if(r==1){
return 1;
}else{
return ((n-r+1)/r) * combi(n, r-1);
}
}
덧글 : 재귀함수는 비교적 간단하게 함수를 구현할수 있다.
위의 예에서 주석부분을 제외하면 실제로 combi() 함수는
실제로 100글자를 넘지 않는다.
하지만, 매번마다 함수를 호출하여 메모리를 잡아먹게 되므로,
실제 재귀구조를 이용하는데에는 신중해야할 필요가 있다
