간편 조합 Combination (java)

간편 조합

{A,B,C,D} 4개의 원소중 3개를 뽑을 조합은 어떻게 될까?

조합은 뽑은 원소가 중복되면 안되기 때문에 앞에서부터 차례대로 원소를 뽑아본다.

단순하게 for 를 3번 돌면 된다.

// 4개중 3개를 뽑을경우

int n = 4;

for(int i=0;i<n;i++)

for(int j=i+1;j<n;j++)

for(int k=j+1;k<n;k++){

System.out.print(array[i]+" "+array[j]+" "+array[k]);

System.out.println();

}

결과

A B C

A B D

A C D

B C D

2개를 뽑을땐 for를 2번 반복, 4개를 뽑을땐 for를 4번 반복한다. 몇 개를 뽑을지 모르는데 매번 이렇게 할 수 없다. 또한 for 문이 비슷하게 반복되지 않는가.

코드를 잘 보면 for 한번이 원소 하나를 고르는 행위를 하는 것임을 알 수 있다.

그렇다면 for문으로 원소 한개를 고르고 다시 자기 자신을 호출해 남은일을 넘기는 재귀를 구성해본다. 

위 for 문이 몇개를 뽑을지에 따라 반복된다. 즉 n개중 r개를 뽑는다면 for 는 r만큼 반복되어야 한다.

하나를 뽑으면 그다음에 뽑을 수 있는 개수는 한개 줄어든다. 그렇게 뽑다가 뽑을 수 있는 개수가 0이 되면 r개만큼 뽑은것이다. 더이상 뽑지 않고 출력한다.

이후에는 마지막에 뽑았던 것을 빼놓고 다음에 뽑을 수 있는 것을 뽑는다. 다음것도 뽑을 것이 없다면 다음것을 뽑을 수 있을때까지 마지막을 뺀다. 

조합의 작업을 다음 입력들의 집합으로 정의한다.

1. 원소들의 총 개수

2. 더 골라야 할 원소들의 개수

3. 지금까지 고른 원소들의 번호

위 3가지를 고려해 for 반복 for 문 작업을 하는 재귀함수로 구성한다.

import java.util.Stack;

public class Combination_1 {

static char array[] = {'A','B','C','D'};

public static void main(String[] args) {

Stack<Integer> st = new Stack<Integer>();

for(int i=1; i<=array.length; i++){

System.out.println(i+"개 뽑을경우 조합");

pick(array.length, st, i);

}

}

static void pick(int n,Stack<Integer> st,int r){

if(r==0)

printPick(st);

int smallest = st.isEmpty() ? 0 : st.lastElement() + 1; 

for(int next = smallest; next < n; next++){

st.push(next);

pick(n,st,r - 1);

st.pop();

}

}

static void printPick(Stack<Integer> st){

for(int i:st)

System.out.print(array[i]+" ");

System.out.println();

}

}

결과 

1개 뽑을경우 조합

A 

B 

C 

D 

2개 뽑을경우 조합

A B 

A C 

A D 

B C 

B D 

C D 

3개 뽑을경우 조합

A B C 

A B D 

A C D 

B C D 

4개 뽑을경우 조합

A B C D