[Java] 조합(Combination)

조합(Combination)

• 서로 다른 n개 중에서 r개를 선택하는 경우의 수(순서X, 중복X)
  • 예) 서로 다른 4명 중 주번 2명을 뽑는 방법

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

int n = 4;
int r = 2;

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

int rResult = 1;
for(int i = 1; i <= r; i++) {
    rResult *= i;
}
System.out.println("결과 = " + (pResult / rResult));    //6 출력

중복 조합

• 서로 다른 n개 중에서 r개를 선택하는 경우의 수(순서X, 중복O)
  • 예) 후보 2명, 유권자 3명일 때 무기명 투표 방법

nHr = n+r-1Cr

//함수로 만들어 이용
public int getCombination(int n, int r ){
    int pResult = 1;
    for(int i = n; i >= n - r + 1; i--) {
        pResult *= i;
    }
    int rResult = 1;
    for(int i = 1; i <= r; i++) {
        rResult *= i;
    }
    return pResult / rResult;
}


int n = 2;
int r = 3;

System.out.println(getCombination(n + r - 1, r));    //4 출력

조합 Practice

//1, 2, 3, 4를 이용하여 세자리 자연수를 만드는 방법(순서X, 중복X)의 각 결과를 출력하는 함수를 구현하시오.

void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
	if(r == 0) {
    	for(int i = 0; i < n; i++) {
        	if(visited[i]) {
            	System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
        return;
    }
    
    if(depth == n) {
    	return;
    }
    
    visited[depth] = true;
    combination(arr, visited, depth + 1, n, r - 1);
    
    visited[depth] = false;
    combination(arr, visited, depth + 1, n, r);
}