[순열]04. 순열의 구현 3

다음으로 알아볼 순열 작성 방식은 next permutation을 이용하는 방법이다. next permutation은 말 그대로 사전 순으로 다음의 순열을 찾는 과정이다.

다음 순열이란 만약 요소가 {1,2,3}일 때 이것의 다음은 {1,3,2}, 다시 {1,3,2}의 다음은 {2,1,3} --> {2,3,1} --> {3,1,2} --> {3,2,1}로 전개되는 것을 말한다.

어떻게 이과정이 진행되는지 살펴보자.

진행 과정

next permutation을 찾는 과정은 몇 가지 절차를 거쳐서 이뤄진다. 

{3, 5, 1, 9, 7}로 이뤄진 배열의 다음 순열을 찾아보자.

step 1: src[i]< src[i+1] 즉 다음 요소보다 작은 요소 중 가장 마지막 요소를 찾는다. 다음 그림을 보면 현재 위 조건에 만족하는 인덱스는 0과 2인데 그 중 2가 더 크므로 i=2가 그 대상이다.

만약 1가 존재하지 않는다면 그것은 마지막 순열이다. 

setp2: 맨 뒤에서 부터 i 앞까지 순회하면서 src[i]보다 큰 마지막 요소(처음 발견한 요소)를 찾는다. 이 요소의 index를 j 라고 하자.

step3: 이제 i와 j의 위치를 바꾼다.

step4: 이제 357XX의 처음이므로 7 뒤를 오름차순 정렬한다. 이는 기존 요소들을 reverse 시켜주면 된다.

그래서 {3, 5, 1, 9, 7}의 다음 순열은 {3, 5, 7, 1, 9}가 된다.

이상으로 다음 순열을 구하는 방법을 알아봤다. 이 방법으로 전체 순열을 구하려면 오름차순으로 정렬된 상태의 맨 처음 순열에서부터 step1에서 이야기 했던 base rule이 될때까지 반복하면 된다.

자바 코드

private static boolean nextPermutation() {
        // step1: src[i]<src[i+1]중 가장 뒤의 요소 찾기 - 뒤에서 찾아옴
        int i = src.length - 2;// 외부에서 쓸 변수이므로 밖에 정의
        for (; i >= 0; i--) {
            if (src[i] < src[i + 1]) {
                break;
            }
        }
        // 만약 위 조건을 만족하는 i가 없다면 이미 마지막 순열이므로 다음 순열을 없음
        if (i < 0) {
            return false;
        }
        // step2: i 뒤의 요소들 중에서 src[i] 보다 큰 가장 마지막 녀석 찾기
        int j = src.length - 1;
        for (; j > i; j--) {
            if (src[i] < src[j]) {
                break;
            }
        }
        // step3: i와 j swap
        swap(src, i, j);
        // step4: i뒤의 요소들을 reverse
        for (int a = i + 1, b = src.length - 1; a < b; a++, b--) {
            swap(src, a, b);
        }

        return true;
    }

 

위의 nextPermutation 을 이용해서 순열을 구해보자.

    private static void makePermutation() {
        do {
            System.out.println(Arrays.toString(src));
        } while (nextPermutation());
    }

전체 순열을 구할 때 처음은 정렬된 상태에서  makePermutation을 호출하므로 do ~ while 문장을 사용했다.

next permutation은 c++에는 기본 라이브러리로 제공되는 기능인데 자바에서도 있었으면 좋겠다. ㅜㅜ