순열 구현

순열 구현

 

특정 자료의 집합이 주어질 때, 해당 집합의 자료를 순서를 고려해서 N개 선택하는 경우의 수를 구한다.

예를들어 {1, 2, 3}과 {1, 3, 2}는 다른 경우이다.

 

 

 

1. 풀이

1.1 풀이 방법

초기에 주어진 자료집합을 initArray라고 하자.

initArray의 각 원소를 하나의 노드로 볼 때, 노드들을 처음부터 끝까지 재귀적으로 N번 탐색하면서 선택하면 모든 경우의 수를 구할 수 있다.

단, 각 노드는 해당 노드까지 선택된 자료의 정보를 갖고 있어야한다.

 

[중복 선택 불가 예시]

예를 들어 1, 2, 3중 3개를 고르는 경우를 찾을 때 1과 2를 선택한 상황이라고 하자.

그러면 중복이 허용되지 않기 때문에 그다음에 선택될 숫자는 1과 2가 될 수 없다.

따라서 각 노드는 다음 노드로 갈 수 있는지를 판단하기 위해, 해당 노드까지 선택된 자료들의 정보를 갖고 있어야 한다.

 

 

 

1.2 코드

1.2.1 permutation

자료의 집합 initArray에서 choiceNum만큼 자료를 선택하는 경우의 수 구한다(순열).

구해진 경우의 수의 조합을 resultList에 담아 반환하는 메서드

 

[permutation]

public ArrayList<Integer[]> permutation(ArrayList<Integer[]> resultList, Integer[] result, boolean[] check,
                                        Integer[] initArray, int choiceNum, int depth) {
    //depth가 선택할 숫자와 같아지면 depth까지 선택한 숫자가 담긴 배열 result를 복사해서 resultList에 넣어준다.
    if (depth == choiceNum) {
        Integer[] tempResult = Arrays.copyOf(result, result.length);
        resultList.add(tempResult);
        return resultList;
    }

    //선택할 숫자가 담긴 배열 initArray의 길이 만큼 반복문을 돌리며 숫자를 선택한다(노드를 탐색).
    for (int i = 0; i < initArray.length; i++) {
        //만약 initArray[i]가 선택되었던 숫자라면 반복문을 넘긴다.
        if (check[i]) {
            continue;
        }
		//initArray[i]를 선택해서 result에 넣는 부분(노드가 탐색되는 부분)
		result[depth] = initArray[i];
		//initArray의 i번째 원소가 탐색되었음을 체크해준다. 
        check[i] = true;
        permutation(resultList, result, check, initArray, choiceNum, depth + 1);
        //재귀문을 빠져나오면 initArray[i]가 선택되었다는 사실을 초기화하고 반복문을 넘어가야 하기 때문에 check[i]를 false로 변경해준다.
        check[i] = false;
    }
    return resultList;
}

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

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

● check : 해당 배열의 특정 원소가 true라면 그 위치의 initArray의 원소가 선택되었다는 것을 뜻한다.

                  특정 노드까지 선택된 숫자를 파악하기 위한 배열

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

● choiceNum : 선택할 숫자의 개수

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

 

 

1.2.2 결과

[순열 테스트]

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

1부터 5까지의 숫자 중에서 3개의 숫자를 선택하는 경우를 전부 구한다.

 

 

[결과]

 

 

[순열 개수 테스트]

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

5개 중에 3개를 고르는 경우는 5P3 = 60이다.

 

 

[결과]