Next Permutation

조합과 순열을 공부하면서 항상 재귀를 통해 조합 또는 순열을 구했는데 다른 방법이 있었다.

Next Permutation이 바로 그것이다. 말 그대로 다음 순열을 찾는 방법이다.

위와 같은 4가지 단계를 거친다.

오름차순으로 정렬된 배열이 있을 때

1. 맨 뒤에서 탐색하며, 교환할 위치를 찾는다. 뒤에서부터 탐색하면서 i보다 값이 작은 i-1 인덱스를 발견하는 순간 교환할 위치는 i-1이 된다.
2. 찾은 i-1 인덱스의 배열 값과, 교환할 i-1보다 큰 위치 j를 찾는다.
3. 찾은 i-1 자리와 j의 값을 교환한다.
4. 다음 순열을 위해 i번째 인덱스부터 마지막 인덱스까지 배열을 오름차순으로 정렬한다.

	private static boolean np(int[] numbers) {
		
		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;		
		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;
	}