다음 순열 (Next Permutation)

다음 순열이란 주어진 숫자 배열에서 사전 순으로 다음에 오는 순열을 구하는 방법이다. 예를 들어서 배열 [1, 2, 3]이 있다고 가정하면, 다음으로 오는 순열은 [1, 3, 2]가 된다.

구현

탐색 위치 설정

모든 배열 탐색의 시작 지점은 배열의 맨 오른쪽 인덱스 값이다. 그리고 이때 필요한 것은 3개의 변수인데, 각각 피벗, 교환 대상, 교환 이후 정렬의 역할을 가진다. 이를 i, j, k라고 하였다.

int N = arr.length - 1;
int i, j, k;
i = j = k = N;

피벗 설정하기

피벗은 배열의 맨 오른쪽에서 탐색해 나가면서 i - 1 인덱스에 위치한 값이 i보다 더 큰 경우에 i를 감소해 나가며 피벗을 설정한다. 이는 순열이 내림차순으로 모두 정렬되었다고 가정해나가면서 탐색을 진행하다가, 내림차 순으로 정렬이 되지 않은 부분인 i - 1에 위치한 값이 교환 대상이 된다는 의미이다. 그리고 i는 교환 이후의 오름차순 정렬을 위한 기준 위치가 된다. 결과적으로 i - 1이 피벗이 되는 것이다.

예를 들어 [1, 2, 3]의 경우에는 i는 3을 가리키는 인덱스값 2가 되는 것이고, 배열 요소 2에 해당되는 인덱스 값(1)이 피벗이 되는 것이다. 이때 피벗이 되는 인덱스를 찾지 못한다면 계속해서 감소해 나가 i는 자연스럽게 0이 될 것이다. 따라서 i == 0이라면 다음 순열을 만들 수 없는 가장 큰 순열이 되었다는 뜻이 된다.

while (i > 0 && arr[i - 1] >= arr[i]) --i;

// 가장 큰 순열을 만들었기 때문에 종료
if (i == 0) return false;

피벗 보다 큰 값 찾기

배열의 오른쪽 부터 탐색하면서 피벗보다 큰 값을 찾게 되면, 해당 값이 바로 피벗과 교환해야 할 값이 된다. [1, 2, 3]에서 피벗은 2가 되고, 3이 바로 피벗과 교환해야 할 값이 되는 것이다.

while (arr[i - 1] >= arr[j]) --j;

교환

그러면 i - 1과 j를 교환하면 된다.

// 3. 두 위치의 수 교환
swap(arr, i - 1, j);

피벗 오른쪽 요소 정렬

이제 교환 이후 피벗의 오른쪽 요소와 순열의 맨 오른쪽 요소를 교환해나가면 오름차순으로 정렬된다. 오름차순으로 정렬된다는 것이 보장되는 이유는 앞에서 피벗을 탐색해나가면서 이미 지나간 위치는 내림차순 정렬이 되었다는 것이 보장되기 때문이다. 따라서 단순하게 뒤집기만 하면 피벗의 오른쪽에 있는 배열 원소들의 오름차순 정렬을 할 수 있게 된다.

[1, 2, 3]을 대상으로 하면 이 부분이 동작하지 않으므로 [1, 3, 2]의 다음 순열을 구한다고 가정하면 피벗은 1이 되고 교환 대상은 2가 되어 교환해 중간 값은 [2, 3, 1]이 될 것이다. 이때 i는 3을 가리키고 있고, k는 1을 가리키고 있으므로 이 둘을 바꾸면 최종적으로 [1, 3, 2]의 다음 순열인 [2, 1, 3]이 완성된다.

while (i < k) swap(arr, i++, k--);

그리고 이 단계까지 왔다면 결국 현재 주어진 순열에서 다음 순열을 만들었다는 뜻이 되므로 true를 리턴한다.

return true;

시간복잡도

다음 순열을 구하는 시간 복잡도는 O(N)이다. 다만, 이는 메서드 한 번의 실행 시간을 의미한다. 주어진 배열이 완전히 내림차순이 될 때까지 다음 순열을 구하는 경우에는 가능한 순열의 개수만큼 반복되므로 O(N!)의 시간 복잡도를 가진다.

또한 이 알고리즘은 교환 방식(swap)을 사용하기 때문에, 주어진 배열의 전체 요소에 대해 다음 순열을 구해야 한다. 예를 들어, [1, 2, 3]에서 부분 배열 [1, 2]만을 대상으로 다음 순열을 구할 수는 없다.

전체 코드

전체 코드는 다음과 같다.

public class Main {

	public static void main(String[] args) {
		int input[] = {1, 2, 3};
		boolean plag = true;
		
		while (true) {
			if (!plag) {
				break;
			}
			System.out.println(Arrays.toString(input));
			plag = makeNP(input);
		}
	}

    static boolean nextPermutation(int[] arr) {
        int N = arr.length - 1;
        int i, j, k;
        i = j = k = N;
        
        while (i > 0 && arr[i - 1] >= arr[i]) --i;
        
        // 가장 큰 순열을 만들었기 때문에 종료
        if (i == 0) return false;
        
        while (arr[i - 1] >= arr[j]) --j;
        
        swap(arr, i - 1, j);
        
        while (i < k) swap(arr, i++, k--);
        
        return true;
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}