[순열]03. 순열의 구현 2

순열은 앞서 살펴봤던 visited를 이용하는 방식이외에도 여러 가지 방식으로 작성이 가능하다. 여기서는 swap 을 이용해서 순열을 구하는 방식에 대해 살펴보자.

기본적인 컨셉은 아래와 같다.

 - swap: 요소와 요소의 위치를 서로 변경한다.

 - depth: 선택할 수 있는 요소의 범위를 조절한다.

진행 과정

먼저 최초의 배열 {A, B, C, D}가 있고 depth 0에서 swap 되는 단계는 다음과 같을 것이다.

물론 depth0-1인 BACD는 depth0-0 인 ABCD에 대한 모든 하위 depth가 종료된 후 진행될것이다.

이제 depth0-0의 하위인 depth1의 동작을 살펴보자. 첫 번째 자리는 A로 고정된 상태에서 나머지 요소들이 swap 대상이 된다.

이제 depth1-0이 종료되면 두 번째 자리 B가 고정되고 다음 depth2로 넘어간다. (역시 depth1-1, depth-1-2는 depth1-0의 모든 하위 동작이 끝나고 동작한다.)

이제 C가 고정되고 depth가 3이 되면 소기의 목적을 달성했으므로 ABC를 출력해준다.

이제 depth2였던 이전 스택으로 올라가서 다시 C와 D를 swap 하고 depth가 3으로 증가하면 ABD를 출력한다.

 

이제 AB가 고정된 depth2가 종료되고 depth1으로 이동해 B와 C가 swap 해서 이번에 AC가 고정된 depth2가 될것이다.

이런 과정을 거치면 순열이 완성된다.

자바 코드

위 내용을 코드로 살펴보자.

    private static void makePermutation(int r, int depth) {
        if (depth == r) {
            System.out.println(Arrays.toString(Arrays.copyOfRange(src, 0, depth)));
        } else {
            for (int i = depth; i < src.length; i++) {
                swap(src, depth, i);
                makePermutation(r, depth + 1);
                swap(src, depth, i);
            }
        }
    }

    private static void swap(char[] src, int a, int b) {
        char temp = src[a];
        src[a] = src[b];
        src[b] = temp;
    }