순열 bitmasking 코드

알아야 되는 것  

순열을 구현하는 방법은 대표적으로 2가지가 있다. 

1. boolean 배열 

2. 비트마스킹 이용 

이 글을 쓰는 이유는

아래 압축과정 하나를 남기려고 쓴다. 

 

flag에 ( flag| 1<<i )를 대입해서 재귀에 flag 만 넣어주면

원래 상태로 복구해줘야하지만, 

for (int i = 0; i < N; i++) {
	if( (flag & 1<<i)!=0 ) continue; //1이라면 i번째 비트열이 사용중이다. 선택되었다면 pass 
	number[cnt]= input[i];
    
	flag =flag | 1<<i; //값 대입
	permutation( cnt +1, flag);
	flag =flag & 0<<i; //원상복구
	
}

아래와 같이 

재귀에 계산값(flag | 1<< i)을 넣어주면 굳이 flag 값을 안바꿔 줘도 된다. 

for (int i = 0; i < N; i++) {
	if( (flag & 1<<i)!=0 ) continue; //1이라면 i번째 비트열이 사용중이다. 선택되었다면 pass 
	number[cnt]= input[i];
    
	permutation( cnt +1, flag | 1<<i);
}

를 쓸 수있기 때문이다. 

 

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

public class BitMasking_permutation {
	static int N,R;
	static int[] input,number;
	static int totalCnt;
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		N=sc.nextInt();// 2~10개 라면 비트마스킹으로도 가능 
		R=sc.nextInt();
		input =new int[N];
		number =new int[R];
		for (int i = 0; i < N; i++) {
			input[i]=sc.nextInt();
		}
		permutation(0,0);
		System.out.println("총 경우의 수: "+totalCnt);
	}
	private static void permutation(int cnt,int flag) {//선택된 상태의 비트열을 달고 다녀야한다 
		if(cnt==R) {
			totalCnt++;
			System.out.println(Arrays.toString(number));
			return;
		}
		
		//해당 자리에 뽑을 가능한 모든 수에대해 시도(앞자리까지 선택된 수 배제)
		for (int i = 0; i < N; i++) {
			if( (flag & 1<<i)!=0 ) continue; //1이라면 i번째 비트열이 사용중이다. 선택되었다면 pass 
			
			number[cnt]= input[i];
			permutation( cnt +1, flag | 1<<i);
		}
	}
}