Algorithm[Java] | 완전탐색 - 순열

오늘은 조합적 문제에서 활용할 수 있는 순열,조합,부분집합 중 순열에 대해서 알아보겠습니다.

순열

▪️ 서로 다른 것들 중 몇개를 뽑아서 한 줄로 나열 하는 것
▪️ 서로 다른 n개 중 r개를 택하는 순열 -> nPr
▪️ nPr = n(n-1)(n-2)...(n-r+1)
▪️ nPn = n! = n(n-1)(n-2)...2*1

💡 중복 순열, 순열 구현

순열

1. 재귀 + isVisited 배열 활용하는 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class PermutationTest {

	public static int n,r;
	public static int [] picked; // 뽑힌 값들 저장할 배열 
	public static int [] arr;
	public static boolean [] isVisited;

	public static void permutation(int cnt) {
		// 기저조건 : cnt==r
		if(cnt==r) {
			System.out.println(Arrays.toString(picked));
			return;
		}

		for(int i=0;i<n;i++) {
			if(isVisited[i]) continue; // 중복순열이 아니므로 이미 선택했다면 continue 
			isVisited[i]=true; // i번째 원소 방문 처리 
			picked[cnt]=arr[i]; // i번째 원소를 cnt번째에 넣음 -> picked[cnt]에 넣음 
			permutation(cnt+1); // 다음 cnt+1번째 선택하기 위해 재귀 호출 진행 
			isVisited[i]=false; // i번째 원소 방문 해제
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		arr = new int [] {1,2,3,4,5,6};
		n = arr.length; // 배열의 길이가 n 
		r = Integer.parseInt(br.readLine()); // n개 중 뽑아야할 개수 r개 
		picked = new int[r]; // r개 뽑아야 하므로 r개로 초기화 
		isVisited= new boolean[n]; // isVisited는 이미 선택된 수인지 판단하는 배열이므로 n개로 초기화 

		// nPr 시작! 
		permutation(0);
	}

}

2. 재귀 + 비트 마스킹 활용하는 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Permutation_bitMaskingTest {

	public static int n,r;
	public static int [] picked; // 뽑힌 값들 저장할 배열 
	public static int [] arr;

	public static void permutation(int cnt, int flag) {
		// 기저조건 : cnt==r
		if(cnt==r) {
			System.out.println(Arrays.toString(picked));
			return;
		}

		for(int i=0;i<n;i++) {
			if((flag&1<<i)!=0) continue; // i번째 플래그가 0이 아닌 경우 즉, 방문한 경우 continue 
			picked[cnt]=arr[i]; // i번째 원소를 cnt번째에 넣음 -> picked[cnt]에 넣음 
			permutation(cnt+1, flag|1<<i); // i번째 플래그를 1로 만들며 방문처리 및 다음 cnt+1번째 선택하기 위해 재귀 호출 진행 
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		arr = new int [] {1,2,3,4,5,6};
		n = arr.length; // 배열의 길이가 n 
		r = Integer.parseInt(br.readLine()); // n개 중 뽑아야할 개수 r개 
		picked = new int[r]; // r개 뽑아야 하므로 r개로 초기화 

		// nPr 시작! 
		permutation(0,0);
	}

}

[nPn인 경우] 넥퍼 활용하는 방법

nPn을 구할 경우 위의 방법들 보다 훨씬 빠른 넥퍼라는 방법을 활용합니다.

import java.util.Arrays;

public class PermutationNPTest {

	public static void main(String[] args) {
		int arr[] = new int[] {1,2,3,4,5,6};
		
		Arrays.sort(arr); // 오름차순의 형태로 정렬
		
		do {
			// 순열을 이용한 처리
			System.out.println(Arrays.toString(arr));
		}while(np(arr));
	}
	
	public static boolean np(int[] p) { // p : 다음 순열을 원하는 기존 순열의 배열
		//1. 맨뒤쪽부터 탐색하며 꼭대기 찾기
		int N = p.length;
		int i = N-1;
		while(i>0 && p[i-1]>=p[i]) --i;
		
		if(i==0) return false; // 다음 순열은 없음(가장 큰 순열의 형태)
		
		// 2. 꼭대기 직전(i-1) 위치에 교환할 한단계 큰 수 뒤쪽부터 찾기
		int j=N-1;
		while(p[i-1] >= p[j]) --j;
		
		// 3. 꼭대기 직전(i-1) 위치의 수와 한 단계 큰 수를 교환하기
		swap(p,i-1,j);
		
		// 4. 꼭대기 자리 부터 맨 뒤까지의 수를 오름차순의 형태로 바꿈
		int k = N-1;
		while(i<k) {
			swap(p,i++,k--);
		}
		return true; // 순열 완성했다고 말해줌.
	}
	
	public static void swap(int[] p, int a, int b) {
		int temp = p[a];
		p[a]=p[b];
		p[b]=temp;
	}

}

중복 순열

⭐️ 순열에서 isVisited 배열을 사용하지 않으면 중복 허용!!

package permutation정리;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Duplication_PermutationTest {

	public static int n,r;
	public static int [] picked; // 뽑힌 값들 저장할 배열 
	public static int [] arr;

	public static void permutation(int cnt) {
		// 기저조건 : cnt==r
		if(cnt==r) {
			System.out.println(Arrays.toString(picked));
			return;
		}

		for(int i=0;i<n;i++) {
			picked[cnt]=arr[i]; //i번째 원소를 cnt번째에 넣음 -> picked[cnt]에 넣음 
			permutation(cnt+1); // 다음 cnt+1번째 선택하기 위해 재귀 호출 진행 
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		arr = new int [] {1,2,3,4,5,6};
		n = arr.length; // 배열의 길이가 n 
		r = Integer.parseInt(br.readLine()); // n개 중 뽑아야할 개수 r개 
		picked = new int[r]; // r개 뽑아야 하므로 r개로 초기화 

		// nPr 시작! 
		permutation(0);
	}

}