조합(Combination) 알고리즘

조합은 의외로 재미있는 구조이다. 예를들어 지구멸망의 날 수많은 사람들 중 대충 네명만 뽑아서 데려가야 한다고 하자. 순서는 상관없고 그냥 대충 성별상관없이 뽑으면 된다. 그렇다면 조합은 이렇게 된다.

6,000,000,000C4

60억 지구 인구 중, 4명을 뽑는 조합이다. 이를 구하기위해서 고딩때는 60억인 n! 을 팩토리얼 한 숫자를 (r! * (n-r)!) 으로 나눠서 계산하고는 했다. 

하지만, 팩토리얼도 상당한 계산의 부하가 걸리는 작업이다. 컴퓨터로 코딩을 하려면 매력이 떨어진다.

다만 실질적으로 고딩때 잘 안써먹던 조합을 구하는 공식이 있다.

nCr = n-1Cr-1 + n-1Cr

어차피 손으로 풀려면 팩토리얼 분자 분모 작대기 긋고 해야한다. 다만 컴퓨터로 구하게 될때는 간단한 재귀식을 이용하면 된다. 어떠한 조합의 경우에도 오른쪽 조합 두개로 쪼개진다.

이에 대한 직관은 다음과 같다.

원소가 1,2,3 에서 2개를 골라내는 조합이라고 치자.

(1,2) (2,3) (1,3) 세개지 경우가 있는데 이는 다음과 같은 경우 두가지로 쪼개진다.

(1,X) 인 경우와

(X,X) 인 경우이다.

첫번째 경우는 1이 확정되었으므로, 나머지 것만 구하면 된다.다.(n-1Cr-1)

두번째 경우는 첫번째 숫자가 1이 아닌 경우이므로 첫번째 숫자까지 결정해주어야 한다. (n-1Cr)

이 두개의 경우를 더하면 최종적으로 nCr 이 튀어나온다.

항상 조합을 구하는 식은 저 두가지 경우로 쪼개진다. 그리고 n-1Cr-1을 구하는 두가지 경우는 n-2Cr-1 와 n-2Cr-2 경우로 쪼개질 것이다. 이렇게 최종적으로 쪼갤경우가 없을때까지 nC0 = 1 계속된다.

이를 코딩으로 구현하기 위해서는 의외로 쉽다. n과 r이 같을경우와 r이 0인 경우는 무조건 1이니, 이에대한 사항만 처리해주고 나머지는 재귀 코딩에 맞겨버린다.

	public int combination(int n, int r) {
		
		if(n == r || r == 0) return 1;
		else return combination(n - 1, r - 1) + combination(n - 1, r);
		
	}

이게 끝이다. 조합에 대한 모든 경우가 딱 두가지 경우로 나뉘어지기 때문에 위와같은 간단한 식으로 귀결된다.

그렇다면, 실제로 조합의 경우를 구해본다. 만약 (0,1,2)을 내부적으로 가지고 있는 상태에서 두가지를 골라내고 싶으면 (0,1) (1,2) (0,2) 이 튀어 나와야한다. 함수에 대한 시그니처는 다음과 같다.

combination도 항상 두가지 경우가 합쳐져서 나오는 경우다.

1. 이미 앞자리 하나가 정해졌기 때문에 경우 r-1 개로 나머지를 정해야 하는 경우,

2. 그 나머지 경우인 앞자리는 다른걸로 정해졌다고 치고 r개로 정해야하는 경우다.

combination(int[] arr, int index, int n, int r, int target)

순열을 구하는 문제에서처럼 이것저것 교환하면서 알고리즘을 짤수도 있겠지만, 일단 여기서는 0~n까지의 숫자의 조합을 구한다고 친다.

따라서 arr은 여기서는 순열글과는 다르게 안에서 교환하고 하는게 아니기때문에, 안에 데이터는 없다. 그냥 빈공간을 적당히 확보해주면 된다. 샘플에서는 0,1,2,3 네개의 원소를 가지고 계산을 할 예정이니 int[4]배열의 공간을 만들어준다.

index의 경우 벌써 하나가 정해졌으면 배열중 첫번째 원소가 정해졌다는 뜻으로, +1을 해준다. 그리고 하나가 정해졌으므로, r-1 인자를 주어야 한다. 만약, 정해지지 않은 상태라면 배열에 값이 들어가지 않았음을 뜻하므로 index를 증가시키지 않고 찾는 대상도 r 인자를 주어야 한다.

n 조합을 구할 0~n개의 숫자를 설정한다.

r 조합에서 몇개를 추출할것인지 고른다.

target 0~n으로 나열되어있는 원소들의 집합안에 어떤 숫자를 타겟으로 해서 배열에 집어넣을지를 고를때 쓰인다. 즉, 어떤 combination() 함수가 오든, 항상 +1씩 해주어 판별하게 만든다. 실제로 index변수에 따라, 들어가고 말고가 결정된다.

이 안에서 딱 두개를 그냥 나눠서 구하면 된다. 1번경우와 2번경우. 이를 자바코드로 구현해봤을때는 다음과 같다.

	

	public static void combination(int[] arr, int index, int n, int r, int target) {
		if      (r == 0) print(arr, index);
		else if (target == n) return;
		else {
			arr[index] = target;
			combination(arr, index + 1, n, r - 1, target + 1);
			combination(arr, index, n, r, target + 1);
		}
	}//end combination()

위의 코드에서는 n-1, n-2로 줄어드는 대신 target 이 계속해서 + 1이 되고있다. r이 0이되면 조합이 찾아졌다는 뜻으로 더이상 진행하지 않고 조합값 하나를 출력하고, target == n 이 됨은 첫번째 combination()함수가 아닌 두번째 combination()함수의 호출을 뜻한다. 나머지 분기는 앞에서 말한 그대로다.

아래 코드는 별도의 출력함수와 main 메서드 포함 전체 코드이다.

	

package algo;

public class Combination {
	public static void main(String[] args) {
		int[] arr = new int[5];
		combination(arr, 0, 5, 3, 0);
		
	}

	public static void combination(int[] arr, int index, int n, int r, int target) {
		if      (r == 0) print(arr, index);
		else if (target == n) return;
		else {
			arr[index] = target;
			combination(arr, index + 1, n, r - 1, target + 1);
			combination(arr, index, n, r, target + 1);
		}
	}//end combination()
	
	public static void print(int[] arr, int length) {
		for (int i = 0; i < length; i++) System.out.print(arr[i]);
		System.out.println("");
	}
	
}	

 

결과는 다음과 같다.

 

012
013
014
023
024
034
123
124
134
234