01. Factorial, Permutation, Combination

#############

문제

#############

n!, nPr, nCr의 정의가 아래와 같다.

 

n! = n(n-1)(n-2)...1

nPr = n! /(n-r)!

nCr = nPr/r!

임의의 양의정수 n과 r이 주어졌을 때, n!, nPr, nCr 값을 구하는 메서드를 작성하시오.

 

###############

풀이

#############

1. Factorial

factorial은 주로 재귀호출(recursion)을 이용해서 구한다. 구현되는 메서드는 아래와 같다.

 

private long factorial(long n) throws IllegalArgumentException {

if (n <= 0)

    throw new IllegalArgumentException("error:n is negative or zero");

 

    if (n == 1)

    return 1;

    return n * factorial(n - 1);

}

위의 코드로 했을 경우, n의 커지면 stack overflow 에러가 발생할 수 있다. 함수를 계속해서 재귀호출하기 때문에, n이 커져서 호출되는 함수의 수가 많아지면, 함수의 값을 저장해야하는 stack공간이 overflow되는 것이다.

큰 수에 대해서도 이런 에러가 나지 않게 하려면 아래와 같이 평범하게 코드를 짜주면 된다.

 

private long factorial2(long n) {

long fact = 1;

    for (long i = 1; i <= n; i++) {

    fact *= i;

    }

    return fact;

}

혹은, 재귀호출을 하는 부분을, 한번 계산된 값을 배열값에 저장했다가 사용하는(메모이제이션) 방법을 사용하면, 빠르면서도 overflow없이 계산이 가능하다. (아래 코드)

         private long factorial3(int n) {

                  if (n <= 0)

                           throw new IllegalArgumentException("error:n is negative or zero");

                 

                  long[] fact = new long[n+1];

                  fact[1] = 1;              

                  for(int i=2;i<=n;i++){

                           fact[i] = i * fact[i-1];

                  }

                 

                  return fact[n];

         }   

2. Permutation

Permutation은 n개 중에서 r개를 뽑아서 일렬로 줄을 세우는 것을 말한다.

식은, n!/(n-r)! 이고, 위에서 짠 factorial메서드를 이용하면 될 것이다.

 

그런데, factorial을 이용하지 않고도 가능한다. --> 점화식을 만들어서 재귀호출 사용하게 하려 함이다.

nPr  = n(n-1)(n-2)...(n-r+1) 이므로,

nPr = n * (n-1)P(r-1) 이라고 할 수 있다.  

왜냐면  n * (n-1)P(r-1) = n * (n-1)*(n-2) ...(n-1-r+1+1) = n*(n-1)*(n-2)...(n-r+1) 로, 원래의 nPr의 공식과 같기 때문.

 

또한, nP1은 n이다. (왜냐면 nP1 = n! / (n-1)! = n)

 

따라서, nPr = n * (n-1)P(r-1)이고, nP1=n을 이용하면, Permutation의 계산을 재귀호출을 써서 할 수 있겠다.

  Base 조건: nP1=n

  점화식: nPr = n * (n-1)P(r-1) 

코드는 아래와 같이 된다.

 

private long permutation(long n, long r) throws IllegalArgumentException {

if (n <= 0 || r <= 0)

    throw new IllegalArgumentException("error:n,r are negative or zero");

 

    if (r == 1)

       return n;

    return n * permutation(n - 1, r - 1);

}

 

3. Combination

 

Combination은 n개 중에서 r개를 뽑는 방법의 수를 말하고, 표기는 nCr로 한다.

공식은 nCr = nPr / r!

 

예를 들어, {a,b,c,d} 중에서 2개를 뽑는 방법은, ab, ac, ad, bc, bd, cd 로 6개이다.

공식에 의해 계산해보면, 4P2 = 4P2 / 2! = 4 * 3 / 2 = 12/2 = 6

 

Combination을 구하는 코드를 위 공식(nPr/r!)을 이용해서 짜면 다음과 같다.

 

private long combination(long n, long r) throws IllegalArgumentException {

if (n <= 0 || r <= 0)

    throw new IllegalArgumentException("error:n,r are negative or zero");

 

    return permutation(n, r) / factorial(r);

}

 

 

#####

소스

#####

테스트 코드를 포함한 전체 소스는 아래와 같다.

 

package p1;

 

import java.math.BigInteger;

 

/**

 * n! = n(n-1)(n-2)...1

 * nPr = n!/(n-r)!

 * nCr = nPr/r!

 *

 * ex) 5! = 5 * 4 * ... *1 = 120 5P2 = 5!/(5-2)! = 5*4 = 20 5C2 = 5P2/2! = 10

 *

 * @author  rhaoslikesan

 */

public class NumberOfCases {

        

         public NumberOfCases(){

                  test();

         }

        

         public static void main(String[] args) {

                  new NumberOfCases();              

         }

        

         private void test(){

                  long n,r;

                  long result;

                 

                  n=5;

                  r=2;

                 

                  result = factorial(n);

                  System.out.println(n+"! = "+result);

                 

                  result = permutation(n,2);

                  System.out.println(n+"P"+r+" = "+result);

                 

                  result = combination(n,2);

                  System.out.println(n+"C"+r+" = "+result);

         }

 

         private long factorial(long n) throws IllegalArgumentException {

                  if (n <= 0)

                           throw new IllegalArgumentException("error:n is negative or zero");

 

                  if (n == 1)

                           return 1;

                  return n * factorial(n - 1);

         }

 

         private long factorial2(long n) {

                  long fact = 1;

                  for (long i = 1; i <= n; i++) {

                           fact *= i;

                  }

                  return fact;

         }

         private long factorial3(int n) {

                  if (n <= 0)

                           throw new IllegalArgumentException("error:n is negative or zero");

                 

                  long[] fact = new long[n+1];

                  fact[1] = 1;              

                  for(int i=2;i<=n;i++){

                           fact[i] = i * fact[i-1];

                  }

                 

                  return fact[n];

         }

 

         private long permutation(long n, long r) throws IllegalArgumentException {

                  if (n <= 0 || r <= 0)

                           throw new IllegalArgumentException("error:n,r are negative or zero");

 

                  if (r == 1)

                           return n;

                  return n * permutation(n - 1, r - 1);

         }  

          

         private long combination(long n, long r) throws IllegalArgumentException {

                  if (n <= 0 || r <= 0)

                           throw new IllegalArgumentException("error:n,r are negative or zero");

 

                  return permutation(n, r) / factorial(r);

         } 

}

 

-끝-