[JAVA] 조합(Combination) 구현

[JAVA] 조합(Combination)

부르트포스 유형의 알고리즘을 풀다보면 n개 중에 r개를 뽑아 일일이 함수를 실행해서 결과값을 찾는 문제가 자주 나온다. 이때 조합 함수를 정의하여 사용하며, 기본 형식은 아래와 같다.

void combination(int arr[], int index, int n, int c, int target);

위 함수는 조합의 아래의 기본 공식을 이용한다.

​ = ​ + ​

예를 들어 ​ 인 경우, (1,2) (1,3) (1,4) / (2,3) (2,4) (3,4) 의 경우가 존재하는데

1을 선택하는 경우와 1을 선택하지 않은 경우로 나눌 수 있다.

• 1을 선택하는 앞의 경우에는 1을 이미 선택했으므로, 나머지 3개 중 1개를 고르는 ​ 이 남은 것이고,

• 1을 선택하지 않은 경우는 1을 선택하지 않았았으므로, 나머지 중에 2개를 고르는 ​가 남는 것이다.

즉, ​ = ​ + ​ 가 된다.

위 공식을 이용해 조합의 개수를 구하는 함수는 아래와 같다.

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

조합의 개수를 구하는 것이라 경우의 수 각각을 구하는 함수는 아래와 같다.

java

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

arr[] 은 조합으로 고른 원소가 들어가 있는 배열이다. 배열의 크기는 r과 동일해야 한다.

• 예를 들어 ​의 경우는 arr[] 이 {1, 2}, {1, 3} , ... , {3, 4} 의 원소를 갖고 있을 때 if(r==0) 부분이 실행된다. 해당 조합을 가지고 어떤 기능을 수행할 때에는 arr을 인자로 보내는 함수를 여기서 수행하면 된다.

• int n, int r 은 ​ 의 n, r이 들어가면 된다.

• index는 구한 원소의 개수를 의미한다. 즉, 위처럼 해당 원소를 선택한 경우는 하나의 원소가 선택되었으므로 idnex+1로 인자를 보내주고, r-1개를 뽑으면 되므로 , r-1을 인자로 보내준다. 해당원소를 선택하지 않은 경우는 Index가 그대로 유지되며, r도 그대로 유지된다. (이때는 target만 1 증가한다.)

• target은 몇부터 원소를 선택할지를 의미한다. 예를 들어 ​의 경우를 예로 들 때 target = 1은 (1,2) (1,3) (1,4) 를 말하며, target=2일 경우에는 (2,3) (2,4) .. 를 말한다. index의 원소를 선택하거나 안하거나를 결정했으므로, target을 1 증가시켜준다.

• 
  

combination 함수에서는 (0,1,2) (2,3,4).. 등과 같이 자연수 n의 조합을 출력하므로, 2차원 배열의 좌표와 같은 경우에는 (x,y)를 갖는 객체 리스트를 만들어 놓은 다음 combination 함수를 이용해 자연수 조합을 배열 arr로 받은 다음 이 배열을 리스트에 접근하는 원소로 사용할 수 있다.

소스코드 :

ArrayList<Pos> virus_list = new ArrayList();
for(int i=1; i<=N; i++)
    for(int j=1; j<=M; j++)
        if(map[i][j] == 2) {// 바이러스일 경우 바이러스리스트에 넣기 
            virus_list.add(new Pos(i, j));
            
/*....*/
//virus_list 중 3개를 선택하는 경우
combination(new int[3], 0, virus_list.size(), 3, 0);
    

static void combination(int arr[], int index, int n, int r, int target) {
        if(r == 0) {
            // 좌표 조합 (x,y) 출력
            for(int i=0; i<arr.length; i++) 
                System.out.print("(" + virus_list.get(arr[0]).x + "," 
                                 +  virus_list.get(arr[0]).y + ")");
            System.out.println();
        }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);
        }
    }