다음 순열 - Next Permutation

💡 개념

Next Permutation(다음 순열)은 현재 순열보다 다음으로 큰 순열을 사전 순으로 생성하는 방법.

Next Permutation 방식의 장점:

1) 시간 복잡도: O(N)

• 재귀적 방식은 O(N!) 소요
  

2) 사전순으로 정렬된 순열을 순서대로 구할 수 있다.

• 재귀적 방식은 순서가 일정하지 않지만, Next Permutation은 사전순으로 순열을 차례대로 구할 수 있음

---

🔄 단계별 과정

1. 뒤에서부터 첫 번째 감소하는 위치 찾기(i-1)

while(i > 0 && p[i-1] >= p[i]) i--;
if(i == 0) return false;

배열의 뒤에서부터 시작해서, 첫 번째로 감소하는 위치를 찾는다.
즉, p[i-1] < p[i]인 지점 i를 찾는다. 이때, 배열이 완전히 내림차순이면 더 이상 순열이 없으므로 종료한다.

2. 교환할 위치 찾기 (p[i-1]보다 큰 값 중 가장 작은 값 찾고 교환하기)

int j = size;
while(p[i-1] >= p[j]) j--;
int t = p[i-1];
p[i-1] = p[j];
p[j] = t;

첫 번째 감소 위치 i-1을 찾았다면, 그 위치의 값을 바꿔야 다음 순열로 이동할 수 있다.
이를 위해 다시 배열의 끝에서부터 탐색하여 p[i-1]보다 큰 값 중 가장 작은 값(p[j])을 찾는다.
p[i-1]과 p[j]를 교환한다.

3. 뒤쪽 부분을 정렬
교환 후에는 i 이후의 숫자들을 오름차순으로 정렬해야 한다.
이 부분은 이미 내림차순으로 되어 있기 때문에, 그냥 앞뒤를 뒤집는 방식으로 오름차순을 만들 수 있다.

int k = size;
while(i < k) {
    t = p[i];
    p[i] = p[k];
    p[k] = t;
    i++;
    k--;
}

---

🔍 예제를 통해 이해하기

예시 1: [1, 3, 5, 4, 2] 다음 순열 구하기

1. 감소하는 위치 찾기
위의 배열에서는 5 > 4 > 2 이므로, p[i-1] = p[1] = 3이 첫 번째 감소 위치이다.
따라서 i-1은 1이 된다.

2. 교환할 위치 찾기
이제 p[i-1] = 3보다 큰 값을 찾아서 그 값과 교환해야 합니다. 배열의 끝에서부터 탐색하여, 3보다 큰 값 중 가장 작은 값을 찾는다.
가장 작은 값과 교환하면, 그 뒤의 부분을 최소한으로 변경할 수 있기 때문에 사전순으로 다음 순열이 된다.

결과: [1, 4, 5, 3, 2]

3. 뒤쪽 부분을 정렬
이제 i = 2 이후의 배열 [5, 3, 2]을 뒤집어야 사전순으로 가장 작은 순열이 된다,

[5, 3, 2]를 뒤집으면 [2, 3, 5]가 된다.

최종 결과: [1, 4, 2, 3, 5]

예시 2: [1, 5, 4, 3, 2] 에서 다음 순열 구하기

1. 감소하는 위치 찾기
뒤에서부터 탐색하면, 5 > 4 > 3 > 2 이므로, p[0] < p[1]인 i = 1을 찾는다.
이때 p[0] = 1이고 p[1] = 5이므로, 이 부분이 첫 번째로 감소하는 위치!

2. 교환할 위치 찾기
p[0] = 1보다 큰 값 중 가장 작은 값은 배열의 끝에서부터 탐색했을 때 p[4] = 2이다. 두 값을 교환한다.

결과: [2, 5, 4, 3, 1]

3. 뒤쪽 부분을 정렬
이제 i = 1 이후의 부분[5, 4, 3, 1]은 내림차순으로 정렬되어 있다. 이를 뒤집어서 사전순으로 가장 작은 오름차순으로 만들어야 한다.
5, 4, 3, 1을 뒤집으면 1, 3, 4, 5가 된다.

최종 결과: [2, 1, 3, 4, 5]

---

💻 전체 코드

import java.util.Arrays;

public class NPermTest {
    static int[] p = {1,2,3,4,5};   
    static int N, count;
    
    public static void main(String[] args) {
        N = p.length;
        count = 0;
        
        do {
            count++;
            System.out.println(Arrays.toString(p));
        }
        while (nextPermutation(N-1));
        System.out.println(count);
    }

    static boolean nextPermutation(int size) {
        int i = size;
        // Step 1: Find the largest index i such that p[i-1] < p[i]
        while(i > 0 && p[i-1] >= p[i]) i--;
        if(i == 0) return false;
        
        // Step 2: Find the largest index j such that p[j] > p[i-1]
        int j = size;
        while(p[i-1] >= p[j]) j--;
        
        // Step 3: Swap p[i-1] and p[j]
        swap(i-1, j);
        
        // Step 4: Reverse the sequence from p[i] to the end
        reverse(i, size);
        return true;
    }

    static void swap(int a, int b) {
        int t = p[a];
        p[a] = p[b];
        p[b] = t;
    }

    static void reverse(int start, int end) {
        while(start < end) {
            swap(start++, end--);
        }
    }
}