Next Permutation

Next Permutation: 한 순열에서 사전 순으로 다음 순열 생성

---

알고리즘

1. 배열을 오름 차순으로 정렬한다
2. 뒤쪽 부터 탐색하여 가장 큰 놈을 찾는다(꼭대기를 찾는다, i번째) -> 꼭대기 바로 앞이(i-1번쨰)이 교환 위치(a)
3. 뒤쪽 부터 탐색하여 a와 교환할 a보다 큰 가장 빠른 곳(b)를 찾는다
4. a와 b를 교환한다
5. 꼭대기 부터 맨 뒤까지 정렬한다
6. 2~5번 과정을 반복

꼭대기, a, b 위치

---

코드

 

	//다음 큰 순열이 있으면 true, 없으면 false
	private static boolean np(int[] numbers) {
		//i, j, k 모두 맨 뒤에서 부터 시작
		//비교하는 부분 모두 i-1부터, 
		
		int N = numbers.length;
		//step1. 꼭대기를(i) 찾는다. 꼭대기를 통해 교환위치(i-1)찾는다
		int i = N-1;
		while(i>0 && numbers[i-1]>=numbers[i]) --i;
		
		//맨앞이다 절벽 - 다음은 없어 너가 가장 커
		if(i==0) {return false;}
		
		//step2. i-1위치값과 교환할 큰 값 찾기
		int j = N-1;
		
		//i-1과 교환할 것은 항상 있다
		while(numbers[i-1]>=numbers[j]) --j;
		
		//step3. i-1위치값과 j위치값 교환
		swap(numbers, i-1, j);
		
		//step4. 꼭대기(i)부터 맨 뒤까지 내림차순 형태의 순열을 오름차순으로 처리
		int k = N-1;
		while(i<k) {
			swap(numbers, i++, k--);
		}
		
		return true;		
	}
    
    //위치 교환 함수
    private static void swap(int[] numbers, int i, int j) {
		int temp = numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = temp;
	}