순열 (Permutation) 알고리즘의 모든 것

1~N까지 이루어진 수열을 생각해보자.

 

1 2 3

4 1 3 2

5 4 2 3 1

6 5 1 2 3 4

 

• 크기는 항상 N이 되어야 하고, 겹치는 숫자가 존재하지 않는다.
• 크기가 N인 순열은 총 N!개가 존재한다.

 

 

순열을 사전순으로 나열했을 때 N = 3인 경우에 사전순은 다음과 같다.

1 2 3   - 첫 순열

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1    - 마지막 순열

 

첫 순열은 무조건 오름차순이고, 마지막 순열은 내림차순임을 알 수 있다.

 

 

순열을 사전순으로 나열했을 때, 사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾아보자.

C++ STL의 algorithm에는 이미 next_permutation과 prev_permutation이 존재하기 때문에 사용하면 된다.

(이럴때마다 C++로 갈아타야하나 싶다..)

 

 

먼저, 1부터 7까지의 수를 사전순으로 나열해보자.

1 6 7 5 4 3 2 의 next_permutation은 무엇일까?

 

 

 

그럼, 2 3 1 7 6 5 4 의 next_permutation은 무엇일까?

 

 

약간의 규칙성을 찾았는가? 수가 바뀌는 지점들은 전부 어느부분 이후에 내림차순으로 되어 있는 경우이다.

즉, 사전순으로 정렬한 배열을 A라고 했을 때 A[i-1] < A[i] 로 바뀌는 지점을 찾는게 중요하다. 

A[i-1] < A[i] 인 지점이란 무엇일까.

 

7 2 3 6 5 4 1 의 next_permutation을 찾는 과정을 천천히 살펴보자.

 

 

① 먼저 위의 두 예시로 보아 A[i-1] < A[i] 을 만족하는 가장 큰 i를 찾아야 함을 알 수 있다.

 

그 다음, 그냥 직감적으로 7 2 3 6 5 4 1 의 next_permutation이 무엇이라고 생각드는가?

그렇다. 7 2 4 1 3 5 6 이다. 머릿속에서 그 과정이 어떻게 일어난 것인가?

우리를 '4'라는 숫자를 무의식적으로 찾았다.

 

 

'4'는 '3'보다 크면서 가장 작은 수이다. ('3' 보다 오른쪽에 있는 숫자들 중에서)

그렇다. 그 다음 과정은

② i보다 크면서 A[j] > A[i-1] 을 만족하는 인덱스 번호가 가장 큰 j 를 찾는 것이다. 

 

 

③ A[i-1] 과 A[j]를 swap 한다.

 

④ A[i]부터 순열을 뒤집는다. 즉, 오름차순 정렬 한다. 그럼 next_permutation이 최종적으로 나왔다.

 

 

 

다음 순열(Next Permutation)을 찾는 방법과 각각 걸리는 시간 복잡도를 정리해보자면,

① A[i-1] < A[i] 을 만족하는 가장 큰 i를 찾는다.  → O(N)

② i보다 크거나 같으면서, A[j] > A[i-1] 을 만족하는 인덱스 번호가 가장 큰 j 를 찾는 것이다.  → O(N)

③ A[i-1] 과 A[j]를 swap 한다.   → O(1)

④ A[i]부터 순열을 뒤집는다. (오름차순 정렬)   → O(N)

 

따라서 총 시간복잡도는 O(N) + O(N) + O(1) + O(N) = O(N) 시간이 걸린다.

 

 

 

소스구현 (JAVA)

import java.util.Scanner;
 
public class NextPerm {
    
    public static boolean next_permutation(int[] a) {
        int i = a.length -1;
        // a[i-1] < a[i] 인 시점에서 빠져나올 것임
        while (i>0 && a[i-1] >= a[i]) {
            i -= 1;
        }
        
        if (i<=0)
            return false;
        
        int j = a.length-1;
        // 뒤에서부터 시작해서 a[j] > a[i-1] 인 시점에서 빠져나올 것임
        while (a[j] <= a[i-1]) {
            j -= 1;
        }
        
        // swap 하기 
        int temp = a[i-1];
        a[i-1] = a[j];
        a[j] = temp;
        
        // 현재 상태는 내림차순 되어있으므로
        // i 부터 끝까지 오름차순 정렬하기 
        j = a.length-1;
        while (i<j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }        
        return true;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = i+1;
        }
        
        do {
            for (int i=0; i<n; i++) {
                System.out.println(a[i] + " ");
            }
            System.out.println();
        } while(next_permutation(a));
    }
}