[Java] 순열

1. 개요

지난번에 조합에 이어 순열을 정리해볼려고한다.

알고리즘을 푸는 중 조합 + 순열을 사용해서 푸는 문제가 있었다.

2개 다 까먹어서 한번 더 볼겸 순열을 정리할려고 한다..

2. 목차

- 순열이란?

- Swap을 활용한 순열

- Visited배열을 활용한 순열

 

순열은 어렵지 않으니 간단하게 보고 2가지 방법으로 구현해보자.

3. 본문

1. 순열이란?

순열(Permutation)은 고등학교 때 한번 슬쩍 배웠을 것이다. 간단한 예제를 보자

 

숫자 1,2,3,4를 중복을 허용하지 않고 2개를 뽑는 방법은?

1 2, 1 3, 1 4  |  2 1, 2 3, 2 4  |  3 1, 3 2, 3 4  |  4 1, 4 2, 4 3  -> 총 12개가 된다.

가볍게 생각해보면 4개중 순서 상관없이 2개, 4P2 -> 4 * 3 = 12가 된다.

 

이 처럼 순열은 조합과는 다르게 순서에 상관없이 모든 숫자를 순서대로 뽑는 것이다.

조합은 1,2와 2,1을 같은 것으로 생각한다. 즉, 순서에 상관이 있는 것 이지만 순열을 순서에 상관이 없다.

 

그렇다면 이 것을 어떻게 구현할 수 있을까?

2. Swap을 활용한 순열

Swap은 코딩을 조금이라도 해봤다면 알 수 있다. 배열의 인덱스 값을 바꾸는 것이다.

이번에도 재귀를 활용해 구현할 것이다. 들어가는 배열은 {1, 2, 3}, 3P2를 구현해보자.

    private void perm(int[] arr, int n, int r, int depth){
        if(depth == r){
            //print
            for(int i = 0; i<r; i++){
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        for(int i = depth; i<n; i++){
            swap(arr, depth, i);
            perm(arr, n, r, depth + 1);
            swap(arr, depth, i);
        }
    }

    private void swap(int[] arr, int beforeIdx, int afterIdx){
        int temp = arr[beforeIdx];
        arr[beforeIdx] = arr[afterIdx];
        arr[afterIdx] = temp;
    }

재귀를 이해한다면 쉽게 이해할 수 있을 것이다.

하지만 필자도 재귀를 잘 모르기 때문에 하나씩 적어보자

#1

i = 0 -> swap(0,0), perm(0(depth) + 1)

처음 for문이 다 돌기 전에 perm이 호출된다.

 

#1-1

호출된 perm(1)을 보자.

i = 1 -> swap(1,1), perm(1(depth) + 1), swap후 배열 [1,2,3]

i = 2 -> swap(1,2), perm(1 + 1), swap후 배열 [1,3,2]

perm(2)가 되면 그때의 배열에 맞는 값을 출력한다.

perm(2)가 실행된 후 마지막 swap을 해준다. 이는 값을 원상태로 돌리기 위함이다.

 

#2

우리는 지금까지 #1일때 i = 0을 실행한 것이다.

이제 해줘야 하는건 #1의  i = 1일때 perm을 해줘야 한다. (맨 처음에서 i = 1일 때)

i = swap(0, 1), perm(0(depth) + 1), swap후 배열 [2,1,3]

 

#2-1

마찬가지로 perm(1)이 호출됐다.

i = 1 -> swap(1,1), perm(1 + 1), swap후 배열 [2,1,3]

i = 2 -> swap(1,2), perm(1 + 1), , swap후 배열 [2,3,1]

perm(2)는 위와 마찬가지로 출력이 된다.

 

순열은 구현하기 쉽다는 장점이 있다. 하지만 순서가 보장되지 않는다.

여기서 순서는 [3,1,2], [3,2,1]순이 아닌 [3,2,1], [3,1,2]로 더 큰 수가 먼저 나올 수 있다.

3. Vistied 배열을 활용한 순열

vistied 배열을 활용하면 사전식으로 순열을 찾을 수 있다.

깊이 우선 탐색(DFS)을 통해 모든 인덱스을 방문하고 output 배열에 값을 넣어둔다.

이번도 마찬가지로 {1, 2, 3}, 3P2을 구현해보자.

    static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r){
        if(depth == r){
            for(int i = 0; i<r; i++){
                System.out.print(output[i]);
            }
            System.out.println();
            return;
        }
        for(int i = 0; i<n; i++){
            if(!visited[i]){
                visited[i] = true;
                output[depth] = arr[i];
                perm(arr, output, visited, depth+1, n, r);
                output[depth] = 0;
                visited[i] = false;
            }
        }
    }

output 배열에 데이터를 저장하여 순열을 만든다.

depth(현재 뽑은 수)가 r(내가 뽑고자 하는 수)가 같다면 출력을 해주면 된다.

 

visited[0] = false이므로 if문이 실행된다.

output[0] = arr[0]이 들어가고 재귀를 실행한다. 재귀는 위에서 간단하게 봤으니 넘어가겠다.

마찬가지로 다른 경우의 수도 뽑기 위해서 output과 visited를 돌리면 된다.

3. 마무리

순열을 알고는 있지만 그냥 코드를 외워서 하는 기분이였다.

이번기회에 더 자세히 알아갔으면 좋겠다.