완전탐색 응용, Next Permutation

1. 비트마스킹 순열

package com.algo.day9;

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

public class BitmaskingPermutationTest {
	static int N, R, input[], numbers[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		R = sc.nextInt();
		input = new int[N];	// 입력 수 배열
		numbers = new int[R];	// 순열 저장 배열
		
		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
		}
		
		permutation(0, 0);
	}
	
	public static void permutation(int cnt, int flag) {
		if (cnt == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if ((flag & 1 << i) != 0) continue;	// i인덱스에 해당하는 수가 사용중이면 패스
			numbers[cnt] = input[i];	// 수 선택
			permutation(cnt + 1, flag | 1 << i);	// 다음 수 뽑으러 가기
		}
	}
}

 

---

 

2. Next Permutation

1) Next Permutation란?

- 현 순열에서 사전 순으로 다음 순열 생성

- Next Permutation 사용 전에 숫자 배열을 오름차순으로 정렬하여 가장 작은 순열 한번 처리

 

2) 알고리즘

- 배열을 오름차순으로 정렬한 후 시작한다.

- 뒤쪽부터 탐색하며 교환위치(i - 1) 찾기 (i:꼭대기)

- 뒤쪽부터 탐색하며 교환위치(i - 1)와 교환할 큰 값 위치(j) 찾기

- 두 위치 값(i - 1, j) 교환

- 꼭대기 위치(i)부터 맨 뒤까지 오름차순 정렬

 

3) 순열 코드

package com.algo.day9;

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

public class NPTest {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] input = new int[N];

		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
		}

		// step0 : 정렬(오름차순)
		Arrays.sort(input);
		
		do {
			// 순열 이용한 처리 로직이 여기에..
			System.out.println(Arrays.toString(input));
		} while(np(input));
	}

	// 순열의 뒷쪽부터 작은 변화를 준다!!
	public static boolean np(int[] p) { // 현수열의 사전순 다음 순열 생성(p : 현 순열)
		final int N = p.length;
		// step1 : 교환위치 찾기(뒤쪽부터 꼭대기를 찾으면 꼭대기 이전이 교환위치가 됨)
		int i = N - 1;
		while (i > 0 && p[i - 1] >= p[i]) --i;
		if (i == 0) return false; // 현 순열의 상태가 가장 큰 순열이므로 np가 없다.

		// step2 : 교환위치(i-1)에 넣을 값 뒤쪽부터 찾기(큰 값 중 최소값)
		int j = N - 1;
		while (p[i - 1] >= p[j]) --j;

		// step3 : 교환위치(i - 1) 값과 찾은 위치(j)깂 교환
		swap(p, i - 1, j);

		// step4 : 꼭대기(i)위치부터 맨 뒤까지 오름차순 정렬
		int k = N - 1;
		while (i < k) swap(p, i++, k--);
		
		return true;
	}

	public static void swap(int[] arr, int x, int y) {
		int temp = arr[x];
		arr[x] = arr[y];
		arr[y] = temp;
	}
}