자바로 만드는 조합(Combination) 알고리즘

 :  n개 중에서 r개를 선택하는 방법의 수.

가령 집합 { A, B, C, D } 에서 2명을 순서와 상관없이 선택하는 방법은 어떤 경우가 있을까요?

{A, B}

{A, C}

{A, D}

{B, C}

{B, D}

{C, D}

위와 같이 총 6가지가 있습니다.

지금부터 이런 부분집합을 구하는 방법에 대해서 알아보겠습니다.

아래와 같은 점화식을 이용해 재귀함수로 구현해 볼 것입니다.

일단 점화식에 대해서 알아보자면 n 개중 r 개를 뽑는 방법은

i)  어떤 특정한 원소를 포함하고 뽑았을 때 

ii) 어떤 특정한 원소를 포함하지 않고 뽑았을 때

두가지로 나뉘어 집니다.

i) 어떤 특정한 원소를 포함하고 뽑았을 때는

이제 그특정한 놈 1개는 이미 뽑혔고 제외한 나머지 n-1 개에서 r-1개만 뽑으면 되니깐 경우의 수는 이고

ii) 어떤 특정한 원소를 포함하지 않고 뽑았을 때는

그 특정한 놈이 포함되지 않는 n-1개에서 여전히 r개를 뽑아야하니깐 경우의 수는 가 됩니다.

이러한 원리로 Combination 객체를 만들어보겠습니다.

class Combination{
	private String[] arr;	  //기준 배열
	private Stack<String> st; //조합을 저장할 스택
	public Combination(String[] arr){
		this.arr = arr; 			//배열을 받아 객체에 저장한다.
		st = new Stack<String>();	//스택에 메모리를 할당한다.	
	}
	public void showStack(){
		//스택에 있는 값들을 출력한다.
		for(int i=0;i<st.size();i++){
			System.out.print(st.get(i)+" ");
		}
		System.out.println("");
	}
	
	public void doCombination(int n, int r, int index){
		// n : 전체 개수
		// r : 뽑을 개수
		// index 배열이다보니 현재 배열의 어디를 가리키고 있는지 필요하므로.
		if(r==0){ 
			//0개를 뽑는다는건 더 이상 뽑을 것이 없다는 말과 같으므로  스택을 출력하고 함수를 종료한다.
			showStack();
			return;
		}
		else if(n==r){
			//nCr 이라는 건 나머지를 전부 뽑겠다는 말과 같으므로 전부 스택에 넣은 후 출력하면 된다.
			for(int i=0;i<n;i++)st.add(arr[index+i]);//index부터 n개를 차례대로 스택에 넣고
			showStack(); //스택을 보여준다.
			for(int i=0;i<n;i++)st.pop(); //이후 전부 pop을 시켜 다음 과정을 진행한다.
		}
		else{
			//저 두가지 예외 사항을 빼면 점화식대로 진행하면 된다.
			
			//index를 포함하는 경우
			st.add(arr[index]);
			doCombination(n-1,r-1,index+1); //index를 스택에 넣은상태로 index를 1옮겨 그대로 진행.
			
			//index를 포함하지 않는 경우
			st.pop(); //index를 제거해주고
			doCombination(n-1, r, index+1); //index를 제외한 상태에서 n-1Cr 진행. 
			
			
		}
	}
}

주의할 부분은 위에서 재귀함수가 종료되는, 즉 "선택을 완료한" 시점에서 스택을 출력 해야 하는데 r=0 인 경우와 n=r 인 경우가 있습니다. 자세한 설명은 주석으로 써놓았습니다.

아래는 메인 함수 부분입니다.

public static void main(String[] args) {
		// TODO Auto-generated method stub
	{
		String[] a = {"A","B","C","D"};						
		Combination c = new Combination(a);
		c.doCombination(4, 2, 0);
	}

	}

두둥!!! 

잘 나온 것을 확인할 수 있습니다 ^^