순열

순열 구하기

프로그래머스의 문제 중 [소수 찾기] 라는 문제를 풀다가 순열 알고리즘이 나와서 정리한 내용이다.

1,2,3와 같은 숫자들이 있다. 이것을 중복하지 않고 순서를 끌어내보자.

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

위와 같이 여섯가지의 방법이 존재한다.

1,2,3,4의 경우에는 그 숫자가 훨씬 많아진다. 이를 알고리즘으로 어떻게 구현할 수 있을까?

위의 그림은 ABC 알파벳을 재귀함수를 통해서 순열을 만드는 방법이다.

먼저, ABC 중 첫번째 알파벳을 무엇으로 할 것인가? 종류는 3가지이다. (배열은 ABC 순서로 정해져있다고 가정한다.)

A

B

C

위의 경우에서 첫번째가 A인 경우는 첫번째 인자[0]인 A를 첫번째 인자[0] A와 바꾼 것이다. (실질적으로는 바뀐게 없음.)

첫번째 인자가 B로 설정되어 있는 경우는 첫번째 인자[0]인 A를 두번째 인자[1] B와 바꾼 것이다.

첫번째 인자가 C로 설정되어 있는 경우는 첫번째 인자[0]인 A를 세번째 인자[2] C와 바꾼 것이다.

[0] <-> [0]

[0] <-> [1]

[0] <-> [2]

첫 번째 인자가 고정되었으니 두 번째와 세 번째 인자에 대해서는 위와 같은 과정을 반복하면 된다.

[0] <-> [0] 이 경우에 한해서 확인해보자. A인 경우.

[0][1] <-> [0][1] : 두번째 인자 [1]인 B와 두번째 인자 [1]인 B를 바꾼다. A B C

[0][1] <-> [0][2] : 두번째 인자 [1]인 B와 세번째 인자 [2]인 C를 바꾼다. A C B

마지막 경우를 살펴보자.

[0][1] <-> [0][1] 이 경우에 한해서 확인해보자.

[0][1] [2] <-> [0][1] [2] 바뀌는 건 없다. A B C

[0][1] <-> [0][2] 이 경우에 한해서 확인해보자.
[0][2] [1] <-> [0][2] [1] 바뀌는 건 없다. A C B

nPk의 순열을 구한다.

즉, n개 중 k개로 이루어진 순열을 구하려 한다.

perm(int[] arr, int depth, int n, int k)

• 배열 arr : 계속해서 데이터를 들고다니며 교환되고 있는 배열이다.
• depth : 현재 트리구조에서 어떤 깊이에서 교환 작업을 하고 있는지에 대한 변수이다. 즉, 맨처음 깊이라면 0의 위치에서 작업을 하고 있을 것이며 이는
  첫 번째와 첫 번째 인자를 교환하거나(1,2,3,4)
  첫 번째와 두 번째 인자를 교환하거나(2,1,3,4)
  첫 번째와 세 번째 인자를 교환하거나(3,1,2,4)
  첫 번째와 네 번째 인자를 교환하는 중이다.(4,1,2,3)
• n : 총 배열 안에 들어 있는 숫자를 뜻하며, 배열의 길이이다. 고정 값이다.
• k : 몇 개를 뽑아내서 순열을 만들 것인지를 뜻하며 고정 값이다.

private static void perm(int[] arr, int depth, int n, int k) {
        if (depth == k) {
            print(arr, k);
            return;
        }

        for (int i = depth; i < n; i++) {
            swap(arr, i, depth);
            perm(arr, depth + 1, n, k);
            swap(arr, i, depth);
        }
    }

depth를 검사해 k와 같으면 더이상 순열을 만들지 않는다. 내가 원하는 건 k개의 숫자가 있는 순열이기 때문이다. 여기서는 4에 도달하면 출력해야 하는 숫자 4개가 세팅되었다는 뜻이므로 출력하면 된다.

depth에 따라서 for문의 시작점이 다르다. depth가 0이라면 1XXX, 2XXX, 3XXX, 4XXX를 뽑아줘야 하기 때문에 총 네번의 루프가 돌아야 한다.

depth 0 -> 1XXX이 만들어지면, 여기서 재귀 함수를 통해서 perm을 호출하고 그 안의 depth 호출은 아래와 같다.

depth 1 -> 2XXX를 만드는 것이 아니라 12XX, 13XX, 14XX을 만들고

depth 2 -> 다음으로 123X

depth 3 -> 1234이 채워지며

depth 4 -> 출력한다.

depth 0 -> 2XXX이 만들어지고 위의 과정을 반복한다.

또한, 위의 코드에서는 swap 함수를 한번 더 호출한다. 처음에 등장하는 swap을 통해서 원본 배열의 순선를 바꾸고 있다. 따라서 다음에 순열을 만들려고 할 때 값이 바뀌기 때문에 제대로 된 값을 만들 수 없다. 그래서 원본 배열로 다시 복귀하는 것이다.

Ex)

1 2 3 4 에서 [1] <-> [2]을 바꿔서 1 3 2 4가 된다.

여기서 재귀호출을 하여 끝까지 탐색하고 결과를 출력하고 돌아오면 배열은 1 3 2 4이다.

이제 [1] <-> [3]을 바꿔서 1 4 3 2을 처리해야 하지만 실제로는 1 4 2 3 이 된다.

따라서 예상하지 못한 배열이 처리된다. 따라서 바뀐 배열을 원래의 배열로 돌려줘야 한다.

최종 Code

private static void perm(int[] arr, int depth, int n, int k) {
        if (depth == k) {
            print(arr, k);
            return;
        }

        for (int i = depth; i < n; i++) {
            swap(arr, i, depth);
            perm(arr, depth + 1, n, k);
            swap(arr, i, depth);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void print(int[] arr, int k) {
        for (int i = 0; i < arr.length; i++) {
            if (i == k - 1) System.out.println(arr[i]);
            else System.out.print(arr[i] + ", ");
        }
    }

참고

• 순열(PERMUTATION) 알고리즘