알고리듬 - Next Permutation

Permutation 관련 문제를 푸는데 더 빠른시간에 푼 코드를 확인해보니 Next Permutation(NP)을 사용하고 있었다.

 

특정 조건을 만족한다면 NP를 활용하는 것이 좋아보여서 이에 대한 내용을 작성하고자 한다.

 

다음 순열(Next Permutation)

Next Permutation(이하 NP)은 순열을 순차적으로 탐색하는 알고리듬이다.

 

특징

• 재귀를 활용하지 않는다. 재귀를 활용한 순열 탐색보다 속도가 빠르다.
• 사전 순 정렬이 된 상태에서 탐색을 시작해야 온전히 모든 순열을 구할 수 있다.
• 특정 개수의 순열을 뽑을 수 없다.

 

동작 과정

NP의 동작 과정은 아래와 같다.

1. 배열의 가장 오른쪽에서 시작해 왼쪽으로 가며 값이 작아지는 순간의 인덱스(Pivot)을 구한다.
2. 배열의 가장 오른쪽에서 시작해 Pivot보다 크면서 가장 작은 값의 인덱스를 구한다.
3. 둘의 위치를 Swap한다.
4. Pivot 기준 오른쪽을 오름차순으로 정렬한다.

 

글로만 보면 이해하기 어려우니 그림과 함께 다시 보자.

현재 순열은 아래와 같고 우리는 다음 순열을 구해야 한다.

 

1. 배열의 가장 오른쪽에서 시작해 왼쪽으로 가며 값이 작아지는 순간의 인덱스(Pivot)을 구한다.

6에서 3이될 때 값이 작아지므로 2번 인덱스가 Pivot이다.

 

2. 오른쪽에서부터 Pivot보다 크면서 가장 작은 값의 인덱스를 구한다.

4번 인덱스의 값이 5로 3보다 크면서 가장 작은 값이다.

 

3. 둘의 위치를 Swap한다.

 

4. Pivot 기준 오른쪽을 오름차순으로 정렬한다.

 

위 과정을 통해 우리는 다음 순열을 구했다.

 

실제로 코드로 보면 1 4 3 6 5 2 다음은 1 4 5 2 3 6이다.

 

이제 코드를 살펴보자.

 

코드

1. main

배열엔 1 ~ 4가 사전순으로 되어있고 do-while문을 활용해 NP를 돌릴 것이다.

nextPermutation 메서드의 반환이 false일 때까지 반복한다.

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4};
		do {
			System.out.println(Arrays.toString(arr));
		} while (nextPermutation(arr));
	}

 

2. swap

단순한 swap 메서드이다. 필요할 때마다 호출해서 위치를 바꿀 것이다.

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

 

3. nextPermutation

아래는 NP의 전체 코드이다. 

	static boolean nextPermutation(int[] arr) {
		int length = arr.length - 1;
		int i = length - 1;
		// 1. pivot 구하기
		while (i >= 0 && arr[i] > arr[i + 1]) {
			i--;
		}

		// 1.1 pivot을 구하지 못하면 종료
		if (i == -1) {
			return false;
		}
		
		// 2. pivot 인덱스 값보다 큰 값 중 가장 작은 값 구하기
		int j = arr.length - 1;
		while (arr[i] > arr[j]) {
			j--;
		}

		// 3. swap
		swap(arr, i, j);

		
		// 4. pivot 기준 오른쪽 오름차순 정렬
		int k = arr.length - 1;
		i++;
		while (k > i) {
			swap(arr, i++, k--);
		}

		return true;
	}

 

코드를 뜯어보자.

 

1. pivot 구하기

가장 오른쪽에서 시작해 i가 0보다 작아지거나 배열의 값이 작아지는 순간까지 i--를 한다.

		int length = arr.length - 1;
		int i = length - 1;
		// 1. pivot 구하기
		while (i >= 0 && arr[i] > arr[i + 1]) {
			i--;
		}

 

1.1 pivot을 구하지 못한 경우

pivot을 구하지 못했다는 것은 배열의 값이 작아지는 순간을 찾지 못했다는 것이고

이는 내림차순으로 정렬되었다는 의미이므로 false를 반환하고 이로써 NP가 종료된다.

		// 1.1 pivot을 구하지 못하면 종료
		if (i == -1) {
			return false;
		}

 

2. pivot 인덱스 값보다 큰 값 중 가장 작은 값 구하기

pivot을 구했으면 해당 값을 기준으로 큰 값 중 가장 작은 값을 구해야 한다.

우리는 궁극적으로 오름차순에서 내림차순으로 변환하는 과정이기에

오른쪽부터 확인했을 때 가장 처음 만나는 pivot보다 큰 값이 큰 값 중 가장 작은 값이다.

		// 2. pivot 인덱스 값보다 큰 값 중 가장 작은 값 구하기
		int j = arr.length - 1;
		while (arr[i] > arr[j]) {
			j--;
		}

 

3. swap

위치를 바꾼다.

		// 3. swap
		swap(arr, i, j);

 

4. pivot 기준 오른쪽 오름차순 정렬

모든 순열을 출력하기 위해 오름차순으로 정렬한다.

		// 4. pivot 기준 오른쪽 오름차순 정렬
		int k = arr.length - 1;
		i++;
		while (k > i) {
			swap(arr, i++, k--);
		}

		return true;

 

출력 결과

 

재귀를 활용하는 것보다 시간이 더 빠르기에 쓸만 한 상황이면 계속 활용할 듯하다.

import java.util.Arrays;

public class Practice {

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4};
		do {
			System.out.println(Arrays.toString(arr));
		} while (nextPermutation(arr));
	}

	static boolean nextPermutation(int[] arr) {
		int length = arr.length - 1;
		int i = length - 1;
		// 1. pivot 구하기
		while (i >= 0 && arr[i] > arr[i + 1]) {
			i--;
		}

		// 1.1 pivot을 구하지 못하면 종료
		if (i == -1) {
			return false;
		}
		
		// 2. pivot 인덱스 값보다 큰 값 중 가장 작은 값 구하기
		int j = arr.length - 1;
		while (arr[i] > arr[j]) {
			j--;
		}

		// 3. swap
		swap(arr, i, j);

		
		// 4. pivot 기준 오른쪽 오름차순 정렬
		int k = arr.length - 1;
		i++;
		while (k > i) {
			swap(arr, i++, k--);
		}

		return true;
	}

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