[CS개념] 경우의 수 : 순열(Permutation), 조합(Combination)

🔶 순열

1. 팩토리얼(Factorial)

• 1~n까지 모든 자연수의 곱(n!)
• 누적 곱
• n!

//5!
int n = 5;
int result = 1;
for (int i = 1; i <= n; i++) {
    result *= i;
}
System.out.println("result = " + result);

//Stream 활용
System.out.println(IntStream.range(2, 6).reduce(1, (x, y) -> x * y));

 

2. 순열

• 순서를 정해서 나열함
• 서로 다른 n개 중 r개를 선택하는 경우의 수 (순서O, 중복X)
• nPr = n! / (n-r)!

//5명을 3줄로 세우는 경우의 수
n = 5;
int r = 3;
result = 1;

for (int i = n; i >= n - r + 1; i--) {
    result *= i;
}
System.out.println("result = " + result);

 

3. 중복순열

• 서로 다른 n개 중에 r개를 선택하는 경우의 수(순서O, 중복O)
• nπr = n^r

//서로 다른 4개의 수 중 2개를 뽑는 경우의 수 (중복O)
n = 4;
r = 2;
result = 1;

for (int i = 0; i < r; i++) {
    result *= n;
}
System.out.println("result = " + result);

//Math활용
System.out.println(Math.pow(n, r));

 

4. 원순열

• 원 모양의 테이블에 n개의 원소를 나열하는 경우의 수
• n! / n = (n-1)!

//원 모양의 테이블에 3명을 앉히는 경우의 수
n = 3;
result = 1;

for (int i = 1; i < n; i++) {
    result *= i;
}
System.out.println("result = " + result);

 

🔶 조합

1. 조합

• 서로 다른 n개 중 r개를 선택하는 경우의 수(순서X, 중복X)
  • ex) 서로 다른 5명 중 2명 뽑는 방법
  • nCr = n! / (n-r)!r! = nPr / r!

  //1. 조합
  int n = 4;
  int r = 2;
  
  int pResult = 1;
  for (int i = n; i >= n - r + 1; i--) {
      pResult *= i;
  }
  
  int fResult = 1;
  for (int i = 1; i <= r; i++) {
      fResult *= i;
  }
  
  System.out.println(pResult / fResult);
  

2. 중복조합

• 순서X, 중복O
  • ex) 후보 2명, 유권자 3명일 때 무기명 투표 방법
  • nHr = n + r - 1Cr

int getNumOfCombination(int n, int r) {
    int pResult = 1;
    for (int i = n; i >= n - r + 1; i--) {
        pResult *= i;
    }

    int fResult = 1;
    for (int i = 1; i <= r; i++) {
        fResult *= i;
    }

    return pResult / fResult;
}

//2. 중복 조합
public static void main(String[] args) {
	n = 2;
	r = 3;
	
	int hResult = new Main().getNumOfCombination(n + r - 1, r);
	System.out.println(hResult);
}