[ETC] JAVA - 순열,중복 순열 구현 (비트마스크 활용 포함) - 공룡 루디

 순열

조합에 이어 알고리즘 문제를 풀 때 많이 쓰이는 순열입니다.

 

순열은 조합과 다르게 순서가 중요합니다.

 

순열은 nPr로 표현 할 수 있으며 n개중 r개를 뽑아 나열하는 수열입니다.

 

 

구현할 때 조합과 가장 큰 차이점은

isSelected라는 boolean 배열을 만들었다는 점과

조합은 for구문에서 start부터 시작했는데 순열은 i=0부터 시작합니다.

import java.util.Arrays;

public class BasicPermutation {

	
	static int [] selected;
	static boolean [] isSelected;
	static int count;
	static void makePermutation(int[] arr, int R, int cnt) {
		//순열을 만들때 끝나는 조건 cnt==R일 때
		if(cnt==R) {
			count++;
			System.out.println(Arrays.toString(selected));
		}else {
			for(int i=0;i<arr.length;i++) {
				if(isSelected[i]) continue;
				isSelected[i]=true; //i번째 원소를 선택하고
				selected[cnt]=arr[i]; //i번째 원소를 넣고
				makePermutation(arr, R, cnt+1); // 재귀 호출
				isSelected[i]=false; //i번째 원소 선택 해제
			}
			
		}
	}
	
	public static void main(String[] args) {
		int [] arr = {1,2,3,4,5};
		int R = 3;
		selected = new int[R]; 			//selected는 선택된 원소가 들어갈 배열이므로 R개이다.
		isSelected= new boolean[arr.length]; //isSelected는 arr의 원소의 개수와 같아야한다.
		
		//배열에 속한 N개의 원소들 중 R개를 뽑아 순열을 만들자
		makePermutation(arr,R,0);
		System.out.println("순열의 개수: "+count);
	}

}

 

 

 비트 마스크를 활용한 순열 구현

 

isSelected라는 boolean 배열 대신

비트마스크를 이용하여 순열을 구현 할 수 있습니다.

 

비트마스크란 2진수의 비트로 이루어진 정수와

쉬프트,&,| 연산을 이용해서 i번째의 플래그가 1인지 0인지 확인하는 방법입니다.

 

import java.util.Arrays;

public class Permutation_bit_mast {
	
	static int[] selected;
	static int count;
	
	static void makePermutation(int [] arr,int R, int cnt, int flag) {
		if(cnt==R) {
			count++;
			System.out.println(Arrays.toString(selected));
		}else {
			
			for(int i=0;i<arr.length;i++) {
				if((flag&1<<i)!=0) continue; //i번째 플래그가 1인 경우
				selected[cnt]=arr[i];
				makePermutation(arr, R, cnt+1, flag|1<<i); //i번째 플래그를 1로
			}
		}
		
	}

	public static void main(String[] args) {
		int [] arr = {1,2,3,4,5};
		int R = 3;
		selected = new int[R]; 			//selected는 선택된 원소가 들어갈 배열이므로 R개이다.
		
		//배열에 속한 N개의 원소들 중 R개를 뽑아 순열을 만들자
		makePermutation(arr,R,0,0); // arr R cnt flag
		System.out.println("순열의 개수: "+count);
	}
}

 

 중복순열 구현

중복순열은

순열을 구현할때 isSelected라는 boolean 배열을 사용 안하면 중복을 허용하게 됩니다.

 

public class PermutationWithRepitition {
	static int[] selected;
	static int count;

	static void makePermutation(int[] arr, int R, int cnt) {
		// 순열을 만들때 끝나는 조건 cnt==R일 때
		if (cnt == R) {
			count++;
			System.out.println(Arrays.toString(selected));
		} else {

			for (int i = 0; i < arr.length; i++) {
				selected[cnt] = arr[i]; // i번째 원소를 넣고
				makePermutation(arr, R, cnt + 1); // 재귀 호출
			}
		}
	}

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5 };
		int R = 3;
		selected = new int[R]; // selected는 선택된 원소가 들어갈 배열이므로 R개이다.

		// 배열에 속한 N개의 원소들 중 중복을 허용해 R개를 뽑아 순열을 만들자
		makePermutation(arr, R, 0);
		System.out.println("중복 순열의 개수: " + count); //개수는 n의 r승임
													//n*n*n...*n
	}
}