다음 순열 (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 = nextPermutation(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;
    }
}