Permutation

비트마스킹 사용

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

public class BitmaskingPermutationTest {
	static int N, input[], numbers[];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		input = new int[N];
		numbers = new int[N];
		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
		}
		permutation(0,0);
	}
	public static void permutation(int cnt, int flag) {
		if(cnt == N) {
			System.out.println(Arrays.toString(numbers));
			return; 
		}
		for(int i = 0; i < N;i++) {
			if((flag & (1 << i)) != 0 ) continue; // i번째 인덱스 사용중이면 pass
			numbers[cnt] = input[i]; // 수 선택
			permutation(cnt + 1, flag | (1 << i));
		}
	}
}

nextPermutation

1. 뒤쪽부터 탐색하며 교환 위치(i-1) 찾기
2. 뒤쪽부터 탐색하며 교환 위치(i-1)와 교환할 큰 값 위치 (j) 찾기
   => i-1보다 큰 값 중 가장 작은 값 => 뒤에서 시작해서 첫번째로 만나는 i-1보다 큰 값
3. 두 위치 값 (i-1, j) 교환
4. 꼭대기 위치(i)부터 맨 뒤까지 오름차순 정렬 => 순서 reverse시키면 됨

package algorithm_class;

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

public class nextPermutationTest {
	public static int arr[];
	public static int N;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new int[N];
		for(int i = 0; i < N;i++) {
			arr[i] = sc.nextInt();
		}
		Arrays.sort(arr);
		do {
			System.out.println(Arrays.toString(arr));
		}while(nextPermutation());
		sc.close();
	}
	public static boolean nextPermutation() {
		int i = N-1;
		while(i > 0 && arr[i] <= arr[i-1]) {
			i--;
		}
		if(i==0) return false; 
		int j = N-1;
		while(arr[i-1] >= arr[j]) {
			j--;
		}
		swap(i-1,j);
		int k = N-1;
		while(i < k) {
			swap(i,k);
			i++;
			k--;
		}
		return true;
	}
	public static void swap(int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}

permutation으로 combination 구현

nextPermutation() 안에 0,1을 넣고 이를 flag형식으로 사용