[알고리즘 개념] 순열

순열

서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관 있게 선택하는 것

ex) [1,2,3,4,5] 배열에서 3개를 순서에 상관 있게 선택

결과

 

코드 - visited배열 이용

import java.util.Arrays;

public class PermutationTest {
	static int N = 5, R = 3;
	static int[] arr = {1,2,3,4,5};
	static int[] result = new int[R];
	static boolean[] visited = new boolean[N];
	
	public static void main(String[] args) {
		
		permutation(0);

	}
	
	static void permutation(int cnt) {
		if(cnt == R) {
			System.out.println(Arrays.toString(result));
			return;
		}
		for (int i = 0; i < N; i++) {
        		//중복되는지 체크
			if(visited[i]) continue;
			
			result[cnt] = arr[i];
			visited[i] = true;
			
			permutation(cnt+1);
			visited[i] = false;
		}
	}
}

 

코드 - 비트마스킹 이용

import java.util.Arrays;

public class PermutationTest {
	static int N = 5, R = 3;
	static int[] arr = {1,2,3,4,5};
	static int[] result = new int[R];
	
	public static void main(String[] args) {
		
		permutation(0, 0);

	}
	
	static void permutation(int cnt, int flag) {
		if(cnt == R) {
			System.out.println(Arrays.toString(result));
			return;
		}
		for (int i = 0; i < N; i++) {
        		//중복되는지 체크
			if((flag & 1<<i) != 0) continue;
			
			result[cnt] = arr[i];
			permutation(cnt+1, flag | 1<<i);

		}
	}
}

 

추가코드 - 중복을 허용하는 순열

import java.util.Arrays;

public class PermutationTest {
	static int N = 5, R = 3;
	static int[] arr = {1,2,3,4,5};
	static int[] result = new int[R];
	
	public static void main(String[] args) {
		
		permutation(0);

	}
	
	static void permutation(int cnt) {
		if(cnt == R) {
			System.out.println(Arrays.toString(result));
			return;
		}
		for (int i = 0; i < N; i++) {		
        		//중복 체크하지 않아도 됨
			result[cnt] = arr[i];
			permutation(cnt+1);

		}
	}
}