[Java] 순열 / 조합 / 부분 집합 정리 (수도 코드 - 재귀편)

순열

서로 다른 n개의 원소 중 r개를 순서 있게 골라낸 것을 순열(Permutation)이라고 한다.

아래 코드는 주사위를 3번 던졌을 때 나올 수 있는 경우의 수이다. (중복 X, 순서 O)

	// 순열 : nPr ==> n!
	private static void dice2(int cnt) {
		if(cnt == N) {
			totalCnt++;
			System.out.println(Arrays.toString(numbers));
			return;
		}
		for(int i =1; i<=6; i++) {
			if(isSelected[i]) continue; // 선택 되지 않은 것들만 선택(중복 X)
			numbers[cnt] = i;
			isSelected[i] = true; // 선택
			dice2(cnt+1); // cnt++ 이 아니라 cnt+1 로 해야한다. (cnt 변경되면 안됨.) 
			isSelected[i] = false; // 선택 해제
		}
	}

isSelected 체크를 통해서 중복을 피한다. 중복은 피하지만 1부터 6까지 모두 살펴보므로 순서를 따진다. (예를 들어 123 ,321 이 다른 것으로 여김)

cnt ++ 이 아닌 cnt +1 로 재귀를 호출해야하는 이유는 cnt 자체를 변경(c++)시키면 하나의 순열만 나오기 때문이다.

중복 순열

서로 다른 n개의 원소 중 r개를 순서를 지키며 골라 낸 것 중 중복을 허용 하는 것을 중복 순열(Permutation with Repetition)이라고 한다.

→ 예를 들어 주사위를 3번 던지는 경우의 수에서 111, 666 이 가능하다. (순열은 불가능: 각 자리에 같은 수가 올 수 없다.)

아래 코드는 6개의 숫자 중 3개의 숫자를 출력할 때 나올 수 있는 경우의 수이다. (중복 O, 순서 O)

	// 중복 순열 : nㅠr  ==> n^r 
	private static void dice1(int cnt) {
		if(cnt == N) { // 기저 조건
			totalCnt++;
			System.out.println(Arrays.toString(numbers));
			return;
		}
		for(int i =1; i<=6; i++) { // 유도 파트
			numbers[cnt] = i;
			dice1(cnt+1);
		}
	}

중복을 허용하기 때문에 isSelected 체크를 안해도 된다.

조합

서로 다른 n개의 원소 중 r개를 순서 없이 무작위로 골라낸 것을 조합(Combination)이라고 한다.

아래 코드는 6개의 숫자 중 3개의 숫자를 무작위로 출력하는 경우의 수이다. (중복 X, 순서 X)

	// 조합 nCr : 6C3 : 20
	private static void dice4(int cnt, int start) {
		if(cnt == N) {
			totalCnt++;
			System.out.println(Arrays.toString(numbers));
			return;
		}
		for(int i =start; i<=6; i++) {
			numbers[cnt] = i;
			dice4(cnt+1, i+1);
		}
	}

start를 현재 뽑힌 수의 다음(i+1)으로 재귀를 호출하기 때문에 isSelected 체크를 해주지 않아도 중복이 없고, 자연스럽게 순서가 다른 같은 경우의 수(예를 들어 123, 321, 132 를 같은 경우로 따진다.)도 제거해준다. 

중복 조합

서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것 중 중복을 허용 하는 것을 중복 조합(Combination with Repetition)이라고 한다.

→ 예를 들어 주사위를 3번 던지는 경우의 수에서 111, 222 가 가능하다. (조합은 불가능: 같은 수를 골라낼 수 없다.)

아래 코드는 주사위를 3번 던졌을 때 나올 수 있는 경우의 수이다. (중복 O, 순서 X)

	// 중복조합 nHr : 6H3 : n+1-1Cr : 8C3 : 56
	private static void dice3(int cnt, int start) {
		if(cnt == N) {
			totalCnt++;
			System.out.println(Arrays.toString(numbers));
			return;
		}
		for(int i =start; i<=6; i++) {
			numbers[cnt] = i;
			dice3(cnt+1, i);
		}
	}

 

조합과 다른 점은 재귀를 호출할 때 i+1 을 보내는 것이 아닌 i 를 보낸다는 점이다. 중복을 허용하기 때문에 현재 인덱스부터 재귀를 호출해도 된다. 

부분 집합

공집합을 포함한 모든 원소의 경우의 수를 의미한다. 

예를 들어, {1,2,3} 의 부분집합으로는

{}

{1}

{2}

{3}

{1, 2}

{1, 3}

{2, 3}

{1, 2, 3}

총 8가지가 올 수 있다. 이는 2^3 으로 N개의 원소로 이루어진 부분집합의 총 개수는 2^N 개이다.

입력 받은 자연수들로 부분 집합을 출력하는 코드

import java.util.Scanner;

// 입력받은 자연수들로 가능한 부분집합 구성 : 재귀+boolean배열
public class Sub1_SubSetTest {

	static int N,totalCount;
	static int[] input;
	static boolean[] isSelected;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		input = new int[N];
		isSelected = new boolean[N];
		for(int i=0; i<N; ++i) {
			input[i] = sc.nextInt();
		}
		generateSubSet(0);
		System.out.println("총 경우의 수 : "+totalCount);
	}
	
	private static void generateSubSet(int count) { // count: 현재까지 고려한 원소 수

		if(count==N) {
			++totalCount;
			for(int i=0; i<N; ++i) {
				System.out.print((isSelected[i]?input[i]:"X")+" ");
			}
			System.out.println();
			return;
		}
		isSelected[count] = true;
		generateSubSet(count+1);
		isSelected[count] = false;
		generateSubSet(count+1);
	}

}