[완전탐색][재귀][Bitmask][Java] 순열과 조합, 부분집합에 관하여

순열 (Permutation)

순열이란 서로 다른 것들 중 몇개를 뽑아 한 줄로 나열하는 것을 말한다.

 

쉽게 말하자면 뽑은 수들의 순서가 의미가 있으면 순열이다.

(ex) 반장, 부반장 한명씩 뽑는 경우 : 뽑는 순서에 따라서 다른 의미를 가진다. 

=> ab와 ba는 다르다.

 

순열을 재귀함수로 표현하기 위해서는 해당 인덱스에 해당하는 숫자가 이미 사용중인지 저장하고 있는 별도의 배열이 필요하다. 

만약에 이미 뽑은 인덱스의 경우에는 넘어간다.

 

뽑지 않았다면 해당 수를 저장하고 방문처리를 하고 index+1을 하고 재귀에 들어간다. 

 

이때 주의해야 하는 점은 방문처리를 다시 되돌려야 한다는 점이다. 되돌리지 않는다면 다음 순열을 구할때 영향이 미친다.

 

import java.util.Arrays;

public class Permutation_nPn {
	static int N; // 원소 개수
	static int[] numbers; // 순열을 저장하는 배열
	static boolean[] selected;
	static int tc; // 순열 개수 
	
    private static void permutation(int idx) {
    	// 기저조건 
		if(idx==N) {
			tc++;
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for (int i = 1; i <= N; i++) {
			//중복 검사 (이미 뽑은 경우 넘어간다)
			if(selected[i]) continue;
			
			// 중복되지 않은 경우 
			numbers[idx]=i;
			selected[i]= true;
			permutation(idx+1); // 다음 요소 뽑기.
			selected[i]=false; 
		}
	}
    
	public static void main(String[] args) {
		N=3;
		numbers = new int[N];
		selected = new boolean[N+1];
		permutation(0);
	}
}

 

계산된 결과는 다음과 같다.   

 

순열을 bitmask로 표현하는 방법도 있다.

 

비트 마스크에서 x << y 는 x의 각 비트를 y만큼 왼쪽으로 이동한다는 뜻이다. 오른쪽 빈자리는 0으로 채워진다.

 

따라서 비트 마스크를 통해서 1 과 0 즉 방문 , 비방문을 대신할 수 있다. selected라는 boolean 배열을 사용하지 않아도 비트마스크를 통해서 시간을 좀 더 효율적으로 사용 가능하다.

 

(selected[i]==true) 와 (flag & 1 << i !=0) 은 의미가 같다. 

 

가능한 이유는 재귀를 돌때마다 flag | 1 << i 를 통해 해당 비트에 중복을 체크해주기 때문이다. 

import java.util.Arrays;

public class Permutation {
	static int N; // 원소 개수
	static int[] numbers; // 순열을 저장하는 배열
	static int tc; // 순열 개수
	
    private static void permutation(int idx, int flag) {
    	//기저 조건
		if (idx == N) { 
			tc++;
			System.out.println(Arrays.toString(numbers));
			return;
		}

		for (int i = 1; i <= N; i++) {
			// 중복 검사 
			// flag에 i 숫자를 사용했다고 표시.
            // (1을 i만큼 이동해서 flag랑 비교해서 0이면 방문하지 않은것. 1이면 방문한 것이다.)
			if ((flag & 1 << i) != 0)
				continue;

			// 중복되지 않은 경우
			numbers[idx] = i;
			// flag | 1 <<i 는 i만큼 옮긴거랑 or을 해서 사용했으면 1 체크.
			permutation(idx + 1, flag | 1<<i); // 다음 요소 뽑기.
			
		}
	}
    
	public static void main(String[] args) {
		N = 3;
		numbers = new int[N];
		permutation(0, 0);

	}
}

 

---

조합

조합은 순서가 의미가 없다. 따라서 따로 방문처리를 확인해 줄 boolean 배열이 필요하지 않다.

 

단 이때는 start라는 파라미터가 필요한데 해당 수 이후의 값들로 체크해줘야 하기 때문이다.

 

예를 들어 ( 1 1 2)는 중복 조합이기 때문에 수 중복을 피하기 위해 i+1을 인자로 넘겨준다.

 

만약에 중복 조합을 하고 싶다면 인자로 i 를 넘겨주면 중복 조합이 된다.

import java.util.Arrays;

// nCr
public class CombinationTest {
	static int[] numbers;
	static int N=4,R=2;
    
    static void combination(int cnt,int start) {
		if(cnt==R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for (int i = start; i <=N; i++) {
			numbers[cnt]=i;
			combination(cnt+1,i+1);
		}
	}
    
	public static void main(String[] args) {
		numbers=new int[R];
		combination(0,1);
	}
}

 

4C2 결과는 다음과 같다. 6개

 

 

중복 조합 4H2는 다음과 같다. 10개

 

---

부분 집합

 

모든 부분 집합을 구하려면 각 원소에 대해서 포함하는가 포함하지 않는가를 모두 계산하면 된다.

 

따라서 재귀로 풀려면 한번은 true로 하고 한번은 false로 해서 기저조건까지 반복하면 된다.

 

다음은 백준 1182번 부분 수열의 합 문제의 코드이다. 모든 부분 집합은 isSelected[i]가 true인 것들이고 이를 이용하여 부분 집합의 합을 구할 수 있다.

 

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

public class Main {
	static int N, S;
	static int[] numbers;
	static boolean[] isSelected;
	static int total=0;

	private static void subset(int idx) {
		if(idx==N) {
			int sum=0;
			int selectedCnt=0;
			for(int i=0;i<N;i++) {
				if(isSelected[i]) {
					sum+=numbers[i];
					selectedCnt++;
				}
			}
			
			if(sum==S && selectedCnt >0)
				total++;
			return;
		}
		isSelected[idx]=true;
		subset(idx+1);
		isSelected[idx]=false;
		subset(idx+1);

		
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		numbers = new int[N];
		isSelected = new boolean[N];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++)
			numbers[i] = Integer.parseInt(st.nextToken());
		subset(0);
		System.out.println(total);
	}

}