[알고리즘 이론] 완전 탐색 - Next Permutation

📌 Next Permutation

• 현 순열에서 사전 순으로 다음 순열을 생성
• $_nP_n$만 가능

넥퍼 구현 순서

🕛 시간 복잡도

1. arr[i-1]<arr[i] : $O(N)$
2. arr[i-1]<arr[j] : $O(N)$
3. swap(i-1,j) : $O(1)$
4. arr[k]부터 reverse : $O(N)$

총 시간 복잡도 : $O(N) + O(N) + O(1) + O(N) = O(N)$
즉, 총 $O(N)$의 시간 복잡도를 가진다.

넥퍼 코드

public class Next_Permutation {
		
	public static void main(String[] args) {
		
		int[] arr = new int[] {1,2,3,4,5};
		
		// nPn, n개 뽑기
		
		// 1. 오른차순 정렬 (가장 작은 수로 만들기)
		Arrays.sort(arr);
		// 2. 순열 만들기
		do {                                           
			System.out.println(Arrays.toString(arr));
		}while(np(arr));
		
	}
	
	public static boolean np(int[] arr) {
		
		int N = arr.length;
		
		int i = N-1;
		while(i>0 && arr[i-1]>=arr[i]) --i;  // 뒤에서부터 가장 큰 수(꼭대기) 찾기
		
		if(i==0)return false;
		
		int j = N-1;
		while(arr[i-1] >= arr[j]) --j;       // 뒤에서부터 탐색하여 꼭짓점 바로 직전보다 큰 수 찾기
		
		swap(arr,i-1,j);                     // 찾은 수 swap
		
		int k = N-1;
		while(i<k) swap(arr,i++,k--);					 // 꼭대기부터 맨 뒤까지의 수를 오름차순으로 정렬
		
		return true;
	}
	
	private static void swap(int[] arr,int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

}

넥퍼를 이용한 조합

• 배열의 원소의 자리를 조합하기

1. 조합을 구해야 하는 배열과 같은 사이즈의 0으로 구성된 배열 생성 - combiArr
2. 뽑아야 하는 수 만큼 1로 넣는다, 동시에 오름차순 정렬한다. - $_5C_2$일 때, 00011로 구성
3. 0과 1로 구성된 배열로 넥퍼를 구하고
4. 하나의 넥퍼가 끝나면 원소 1인 위치 찾아, 조합을 구해야 하는 배열에서 동일한 위치의 원소를 출력

public class NP_Combination {
	public static void main(String[] args) {
		int[] origin = new int[] {1,2,3,4,5};
		int[] combiArr = new int[origin.length];    // 0과 1로 구성, 1 이면 해당 자리를 뽑았다고 표현
		int N = origin.length;
		
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();                    // 뽑을 갯수 nCr
		
		int idx =  N;
		while(--idx>=N-r) combiArr[idx]=1;        // 가장 작은 수로 set (오름차순 정렬을 대체)

		do {
			for(int i=0;i<combiArr.length;i++) {	
				if(combiArr[i]==1) {					// 뽑힌 수 출력
					System.out.print(origin[i]+" ");
				}
			}
			System.out.println();
		}while(np(combiArr));
		
	}
	private static Boolean np(int[] arr) {

		int N = arr.length;
		
		int i = N-1;
		while(i>0 && arr[i-1]>=arr[i]) --i;
		
		if(i==0) return false;
		
		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;
	}
	
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

출력
2
4 5
3 5
3 4
2 5
2 4
2 3
1 5
1 4
1 3
1 2