[JAVA] 순열(Permutation)

참고 블로그 : 순열 Permutation (Java) :: 뱀귤 블로그 (tistory.com)

순열 Permutation (Java)

 

순열이란, n개의 후보군 중에서 r개를 선택해서 순서대로 나열하는 것을 말한다.
수식으로 nPr 로 표현하기도 한다.
값은 n!/(n-r)!로 구할 수 있다.
그럼 순열을 통해서 얻을 수 있는 전체 순서쌍은 어떻게 구할 것인가?!🤔

우리가 순열을 구하는 방법

일단 어떻게 코드를 짤지부터 생각하지 말고, 우리가 어떻게 순열을 구하는지를 생각해보자.
'1,2,3 이라는 후보 중에서 3개를 선택하여 순서대로 나열하는 모든 순서쌍을 구하라'는 문제가 주어졌다면,
먼저 우리는 1을 고정하고 2,3 을 나열하여 1,2,3을 구한 다음 2와 3의 순서를 바꾸어 1,3,2 를 구한다.
그리고 1을 고정함으로써 얻을 수 있는 모든 순열을 찾았으므로
2를 고정하고 1,3을 나열하여 2,1,3을 구한다음 1과 3의 순서를 바꾸어 2,3,1을 구한다.
2을 고정함으로써 얻을 수 있는 모든 순열을 찾았으므로
3를 고정하고 1,2을 나열하여 3,1,2를 구한다음 1과 2의 순서를 바꾸어 3,2,1을 구한다.

=> 123, 132, 213, 231, 312, 321

---

코드로 순열을 구하는 방법

코드로 순열을 구하는 방법은 다소 복잡할 수 있으나, 우리가 사고하는 바와 크게 다르지 않다.
코드로 순열을 구하는 방법으로는 1. swap를 이용한 방법 2. visited를 이용한 방법이 있다.

swap 을 이용한 방법

• dept는 고정한 숫자의 수
• dept이후의 것을 기준으로 dept를 제외한 모든 값과 swap하고 dept를 +1해줌
• 더 이상 swap할 것이 없으면 (=dept가 r이 되면) 현재 배열을 출력
• 순열이 완성면, 다시 똑같은 방법으로 swap해서 원상복귀 시킴
• 기준을 잡은 것에 대해 모두 swap을 하고 순열도 완성이 되면, 고정을 해제하고 기준을 바꾸며 이 과정을 반복
• 이때 고정을 하는 것이 dept를 내려가는 것, 고정을 해제하는 것이 dept를 올라가는 것에 대응됨

 

코드

static void permutation1(int[] arr, int depth, int n, int r) {
        if (depth == r) {
            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);
            permutation1(arr, depth + 1, n, r);
            swap(arr, depth, i); // 리턴이 되고 다시 swap해서 배열이 유지되게 함
        }
    }
    static void swap(int[] arr, int depth, int idx){
        int tmp=arr[depth];
        arr[depth] = arr[idx];
        arr[idx] = tmp;
    }

(상세 실행 흐름은 더보기)

실행 흐름

1까지 고정, 2와 2 swap
    12까지 고정, 3과 3 swap => 123, swap 원상복귀
1까지 고정, 2와 3 swap 
    13까지 고정, 2와 2 swap => 132, swap 원상복귀
=> 1에서 만들 수 있는 것 모두 나왔으므로, 1과 2를 swap하여 다시 밑으로 내려가기 시작
2까지 고정, 1과 1 swap
    21까지 고정, 3과 3 swap => 213, swap 원상복귀
2까지 고정, 1과 3 swap
    23까지 고정, 1과 1 swap => 231, swap 원상복귀
=> 2에서 만들 수 있는 것 모두 나왔으므로, 1과 3를 swap하여 다시 밑으로 내려가기 시작
3까지 고정, 2과 2 swap
    32까지 고정, 1과 1 swap => 321, swap 원상복귀
3까지 고정, 2과 1 swap
    31까지 고정, 2과 2 swap => 312, swap 원상복귀

visited 배열을 이용한 방법

• dept는 out에서의 idx를 의미함
• dept=0부터 시작하고, dept==r을 만족하면 전체 배열을 채웠으므로 출력함
• dept에 값을 채우기 위해서는 이전에 사용되었으면 안됨 => visited 배열로 확인
• dept==r을 만족하여 순열을 만든 다음에는 dept==r부터 사용했던 후보의 visited 상태를 false로 바꿈
• 이때, 사용했던 후보의 다음 후보가 true이면 값을 넣을 수 있으므로 재귀함수 호출하여 위의 과정을 반복

코드

static void permutation2(int[] arr, int depth, int n, int r, boolean[] visited, int[] out){
        if(depth == r){
            System.out.println(Arrays.toString(out));
        }

        for(int i=0; i<n; i++){
            if(visited[i] != true){
                visited[i] = true;
                out[depth] = arr[i];
                permutation2(arr, depth+1, n, r, visited, out);
                visited[i] = false;
            }
        }
    }

순서대로 출력하고 싶으면 visited 방법을 쓰면 좋다.

 

후기

제대로 이해하는데에 무려 3시간 정도가 걸렸다..ㅎ
재귀함수와 DFS 개념이 사용된 것이라서 제대로 이해하는데에 시간이 오래 걸린 것 같다.
특히 재귀함수의 실행 순서를 그대로 따라가며 사고하려다보니
재귀함수가 끝나고 다시 돌아오는 부분까지 짚어가며 이해하려 해서 많이 헷갈렸다.
이제는 머릿속에서 단순화해서 암기한 다음 여러 문제에 적용하는 일만 남았다!