조합 구현

조합 구현

 

특정 자료의 집합이 주어질 때, 해당 집합에서 N개를 뽑는 경우를 모두 구하는 코드를 구현한다.

순서는 고려하지 않는다(조합)

예를 들어 {1, 2, 3}과 {1, 3, 2}는 같은 경우로 판단한다.

 

 

 

1. 풀이

1.1 풀이 방법

초기에 주어진 집합을 initArray라고 했을 때, initArray의 원소들을 재귀적으로 탐색하면 N개를 선택한다.

다만 순서를 고려하지 않기 때문에 이전에 탐색한 원소는 탐색하지 않는다.

 

[순열의 탐색]

 

위 그림에서 initArray = {1, 2, 3, 4} 라고 하자.

위 그림은 initArray에서 3개를 선택하는 경우를 찾을 때 탐색되는 방법을 나타낸 것이다.

1을 선택했을 때 순서대로 각 원소를 재귀적으로 탐색하면 위 그림과 같이 1 -> 2 -> 3 순으로 탐색하고  {1, 2, 3}의 경우를 탐색한다.

1을 선택하고 3을 선택했을 때, 3보다 낮은 인덱스의 원소들은 선택할 필요가 없다.

왜냐하면 3 이전 인덱스의 원소들은 이미 탐색되었기 때문에 선택의 경우가 중복되기 때문이다.

위 그림에서 나온 것처럼 1 -> 3 -> 2(3보다 낮은 인덱스)를 선택하면 {1, 3, 2}을 탐색한 것이고 이것은 앞서 탐색된 {1, 2, 3}의 경우와 중복된다.

 

따라서 조합을 구할 때는 재귀적으로 각 원소들을 탐색하되 탐색한 원소보다 낮은 인덱스의 원소는 탐색하지 않는다.

 

 

 

 

1.2 코드

1.2.1 combination

주어진 집합의 배열 initArray에서 choiceNum만큼의 원소를 선택한다.

순서에 상관없이 선택되며 선택된 경우의 집합은 resultList에 넣어지고 resultList가 반환된다.

 

[combination]

public ArrayList<Integer[]> combination(ArrayList<Integer[]> resultList, Integer[] result, 
                                        Integer[] initArray, int choiceNum, int depth, int index) {
    //재귀문의 회수(선택한 회수)가 선택할 개수와 같아지면 탐색된 경우의 집합을 resultList에 넣는다. 
    if (depth == choiceNum) {
        Integer[] tempResult = Arrays.copyOf(result, result.length);
        resultList.add(tempResult);
        return resultList;
    }

    //반복문은 index(= 전 원소의 인덱스 + 1)부터 시작한다.
    for (int i = index; i < initArray.length; i++) {
        result[depth] = initArray[i];
        combination(resultList, result, initArray, choiceNum, depth + 1, i + 1);
    }
    return resultList;
}

● resultList : 주어진 조건에 따라 만들 수 있는 숫자의 조합들이 저장되는 list

● result : 주어진 조건에 따라 만들 수 있는 숫자의 조합이 저장되는 배열

● initArray : 초기에 주어진, 선택해야 할 자료가 있는 배열

● choiceNum : 선택할 숫자의 개수

● depth : 재귀 문의 깊이, 재귀 문이 0부터 시작해서 choiceNum번 돌면 선택할 숫자만큼 숫자가 선택된다.

● index : 전 재귀 문에서 탐색된 원소의 인덱스 + 1 값이 들어온다.

 

순열과 달리 탐색된 원소를 check 하는 배열은 필요 없다.

왜냐하면 항상 탐색된 원소보다 큰 인덱스를 갖는 원소를 탐색하기 때문에 탐색된 원소가 중복될 일이 없기 때문이다.

 

 

[테스트 1]

@Test
public void solutionTest() {
    int choiceNum = 3;
    ArrayList<Integer[]> combination = combination(new ArrayList<>(), new Integer[choiceNum],
            new Integer[]{1, 2, 3, 4, 5}, choiceNum, 0, 0);
    combination.forEach(s -> System.out.println(Arrays.toString(s)));
}

 

[결과]

 

 

 

[테스트 2]

@Test
    public void solutionTest() {
        int choiceNum = 3;
        ArrayList<Integer[]> combination = combination(new ArrayList<>(), new Integer[choiceNum],
                new Integer[]{1, 2, 3, 4, 5}, choiceNum, 0, 0);
//        combination.forEach(s -> System.out.println(Arrays.toString(s)));
        Assertions.assertThat(combination.size()).isEqualTo(10);
    }

 

5C3의 값은 10이 나와야 한다.

 

[결과]