다음 순열 구하기(Next Permutation)

목차

 

 

 

개요

순열 및 조합을 생성할 때 재귀적으로 구현하지 않고 각 인덱스 값을 비교하여 모든 경우의 인덱스 값을 뽑아내는 방법입니다. 

현 순열에서 사전 순(오름차순)으로 다음 순열을 생성합니다. 즉 배열을 가장 작은 값으로 정렬한 뒤, 한 자리씩 swap 하면 서 출력합니다.

 

예시) 1 2 3

1 3 2 
2 1 3 
2 3 1
3 1 2
3 2 1 (가장 큰 값)

 

 

 

장점

• 재귀로 짜여진 순열과 달리 시간 복잡도가 낮습니다. (재귀적 호출이 없고 인덱스의 값만 교체해주므로)
• 순열과 조합을 함께 사용할 수 있습니다.

 

단점

• 원래의 배열을 재배열하여 순열을 만드므로 nPr 과 같이 특정 개수의 순열을 만들 수 없습니다. 

 

 

구현

소스 배열을 오름차순으로 정렬합니다. (1, 2, 3...)

(모든 탐색은 오른쪽에서 왼쪽으로 진행됩니다.)

 

오른쪽에서 왼쪽으로 탐색을 하면서 숫자가 작아지는 부분을 체크합니다. (꼭대기값 찾기, 인덱스 : i)

1 2 4 3

-> 4에서 2로 가는 부분이 숫자가 작아지는 부분입니다.

-> 2의 인덱스인 1을 i-1, 4의 인덱스 3을 i로 저장합니다.

-> 꼭대기값은 i가 됩니다. 만약 i가 0이면 마지막 순열까지 탐색한 것이므로 종료합니다.

 

교환위치를 알기 위해 맨 오른쪽부터 탐색합니다. (인덱스 : j)

j 는 i - 1 보다 큰 값입니다. 탐색을 했다면 j와 i-1의 값을 교체(swap) 합니다.  

1 2 4 3 

-> (i - 1) 은 2입니다. 맨 오른쪽으로 탐색했을 때 3이 2보다 크므로 j는 3이 됩니다. 

-> (i - 1)와 j의 값을 교체합니다.

-> 1 3 4 2

 

교환이 완료되면 꼭대기 값부터 맨 뒤까지 오름차순으로 정렬합니다.

이미 내림차순 정렬되어 있으므로 꼭대기값(i) 부터 맨 오른쪽 값(n-1)의 자리 수를 각각 교환 합니다. 

 

1 3 4 2

-> 꼭대기값(i = 2) 4부터 맨 오른쪽 값(n-1 = 3)의 자리수를 각각 교환

-> 1 3 2 4

 

이런 식으로 가장 큰 순열의 경우의 수가 나올때까지 반복합니다. 

 

 

 

 

 주어진 순열 

 

 

 

꼭대기값 찾기

arr[i-1] < arr[i] 를 만족하는 i-1를 찾습니다.

 

 

arr[i-1]을 기준으로 arr[i-1] 보다 큰 arr[j]를 찾습니다.

j는 맨 오른쪽부터 시작해 왼쪽으로 찾습니다.

 

 

j 의 탐색을 마쳤으면 arr[i-1]과 arr[j]의 값을 교체(swap) 합니다.

 

 

꼭대기값(i)부터 맨 오른쪽 값(n-1) 값을 오름차순 해줍니다. (이미 내림차순이므로 각 자릿수 별로 교체를 진행합니다.)

 

 

 

 

소스코드

import java.util.Arrays;

public class nextpermutation {
	
	public static void main(String[] args) {
		
		int[] arr = {1,4,2,3,};
		
		// 오름차순 정렬 
		Arrays.sort(arr);
		
		
		do {
			System.out.println(Arrays.toString(arr));
		} while(np(arr));
		
	}
	
	public static boolean np(int[] arr) {
		
		int n = arr.length;
		int i = n - 1;
		
		// 꼭대기(i) 탐색
		while(i > 0 && arr[i-1] >= arr[i] ) i--;
		
		// 꼭대기가 0 이면 모든 경우를 탐색햇으므로 종료
		if(i == 0) return false;
		
		// 교체할 데이터 찾기( i-1, j 교체)
		int j = n - 1;
		while(arr[i-1] >= arr[j]) j--;
		swap(arr, i-1, j);
		
		// 꼭대기 값에서부터 맨 오른쪽까지 오름차순으로 변경
		int k = n-1;
		while(i < k) {
			swap(arr, i++, k--);
		}
		
		return true;
	}
	
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

}

 

 

 

 

 

 

 

 

 

참조 사이트

 

https://velog.io/@tomato2532/NextPermutation

[알고리즘] Next Permutation

 

 

https://redbinalgorithm.tistory.com/141

JAVA : nextPermutation 다음순열