[알고리즘] next permutation

Next Permtation

nPn에서 적용 가능하지만, nPr은 불가능하다!!!

package boj;

import java.util.Arrays;
import java.util.Scanner;

public class nextPermutation {
	static int N;
	static int[] input;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		input = new int[N];
		
		for(int i=0; i<N; i++) {
			input[i] = sc.nextInt();
		}
		Arrays.sort(input);//오름차순 정렬하여 가장 작은 순열의 상태로 만듦
		
		do {
			System.out.println(Arrays.toString(input));
		}while(np());
		
	}
	
	
	//NPN, n개중에 r 뽑는 순열은 안된다.
	public static boolean np() {
		
		//STEP 1 : 꼭대기를 찾기 위해 맨 뒤부터!
		int i = N-1;//맨뒤부터 쓴다.
		while(i>0 && input[i-1]>= input[i]) --i; //인접한 두 요소 비교
		
		//더이상 앞자리가 없는 상황 : 현 순열의 상태가 가장 큰 수열(마지막 순열)
		if(i==0) return false;
		
		//STEP 2 : 꺾어지는 곳 교환해야해!
		int j = N-1;
		while(input[i-1] >= input[j]) --j;//교환위치(i-1)와 교환 위치보다 큰수인지 비교한다.
		
		//STEP 3
		swap(i-1,j);
		
		//STEP 4
		int k= N-1;
		while(i<k) {
			swap(i++,k--);
		}
		return true;
	}
	
	private static void swap(int i, int j) {
		int temp = input[i];
		input[i] = input[j];
		input[j] = temp;
	}

}