순열 알고리즘

순열이란?

서로 다른 n개 중 r개를 골라 순서를 고려해 나열한 경우의 수

ex) 1, 2, 3, 4 의 배열에서 두 개의 원소를 고를 때 가능한 경우의 수는

1 2 / 1 3 / 1 4/ 2 3 / 2 4 / 3 4 총 6가지가 나오게 된다.

swap을 이용한 순열 알고리즘

(이미지 출처)

swap 함수를 만들어 배열의 값을 직접 바꾸는 방법

배열의 첫 번째 값부터 하나씩 바꾸며 모든 값을 한 번씩 swap하는 방법이다.

permutation 호출 이후에 swap 메소드를 한 번 더 호출하여 배열의 순서를 보장해준다.

static void permutation(int[] arr, int depth, int n, int r) {
    if(depth == r) {
        print(arr, r);
        return;
    }

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

static void swap(int[] arr, int depth, int i) {
    int temp = arr[depth];
    arr[depth] = arr[i];
    arr[i] = temp;
    
    // 아래는 swap 결과 보기 위해 임의로 추가한 코드
    System.out.print("switch: ");
    for (int num : arr) {
        System.out.print(num);
    }
    System.out.println();
}

static void print(int[] arr, int r) {
    for(int i = 0; i < r; i++)
        System.out.print(arr[i] + " ");
    System.out.println();
}

배열 {1, 2, 3} 이 들어왔을 때 예시

① 한 가지를 고를 때 (n = 3, r = 1)

swap(arr, 0, 0) => 실행 결과 {1, 2, 3} => permutation(arr, 1, 3, 1) => 1 출력 => 배열 {1, 2, 3} 으로 복귀

swap(arr, 0, 1) => 실행 결과 {2, 1, 3} => permutation(arr, 1, 3, 1) => 2 출력 => 배열 {1, 2, 3} 으로 복귀

swap(arr, 0, 2) => 실행 결과 {3, 2, 1} => permutation(arr, 1, 3, 1) => 3 출력 => 배열 {1, 2, 3} 으로 복귀

② 두 가지를 고를 때 (n = 3, r = 2)

swap(arr, 0, 0) => 실행 결과 {1, 2, 3} => permutation(arr, 1, 3, 1) => swap(arr, 1, 1) => 실행 결과 {1, 2, 3} => permutation(arr, 2, 3, 1) => 1 2 출력 => 배열 {1, 2, 3} 으로 복귀 => swap(arr, 1, 2) => 실행 결과 {1, 3, 2} => permutation(arr, 2, 3, 2) => 1 3 출력 => 배열 {1, 2, 3} 으로 복귀

swap(arr, 0, 1) => 실행 결과 {2, 1, 3} => permutation(arr, 1, 3, 1) => swap(arr, 1, 1) => 실행 결과 {2, 1, 3} => permutation(arr, 2, 3, 1) => 2 1 출력 => 배열 {2, 1, 3} 으로 복귀 => swap(arr, 1, 2) => 실행결과 {2, 3, 1} => permutation(arr, 2, 3, 2) => 2 3 출력=> swap(arr, 1, 2) => 배열 {2, 1, 3} 으로 복귀

=> swap(arr, 0, 1) => 초기 배열 {1, 2, 3} 으로 완전 복귀

r = 1 일 때 까지는 이해하기 쉬웠지만, r = 2 부터는 재귀로 깊숙히 들어가기 때문에

직접 디버깅을 돌려 이해해 보는 것이 필요하다.