순열, 중복순열, 조합, 중복조합

• 순열 : n개 중에서 r개를 뽑아서 줄을 세우는 것을 nPr이라고 한다. ( 중복을 허용하지 않는다 )
• 중복 순열 : 순열의 개념 + 중복을 허용한다.
• 조합 : 순열의 개념 - 순서의 차이가 중요하지 않다. ( 중복을 허용하지 않는다 )
• 중복 조합 : 조합의 개념 + 중복을 허용한다.

1. 순열

static void permutation(int cnt){
	if(cnt == N){
		System.out.println(Arrays.toString(numbers));
		return;
	}

	for(int i = 1; i<=6; i++){
		if(!isSelected[i]){
			isSelected[i] = true;
			numbers[cnt] = i;
			permutation(cnt+1);
			isSelected[i] = false;
		}
}

2. 중복 순열

static void repermutation(int cnt){
	if(cnt == N){
		System.out.println(Arrays.toString(numbers));
		return;
	}

	for(int i =1; i<=6; i++){
		numbers[cnt] = i;
		repermutation(cnt+1);
	}
}

3. 조합

static void combination(int start, int cnt){
	if(cnt == N){
		System.out.println(Arrays.toString(numbers));
		return;
	}
	
	for(int i = start; i<=6; i++){
			numbers[cnt] = i;
			combination(i+1, cnt+1);
	}
}

4. 중복 조합

static void recombination(int start, int cnt){
	if(cnt == N){
		System.out.println(Arrays.toString(numbers));
		return;
	}

	for(int i = start; i<=6; i++){
		numbers[cnt] = i;
		recombination(i, cnt+1);
	}
}

---

5. 부분 집합

• 부분 집합 : 어떤 집합에 포함되는 집합을 말한다. 말 그대로 어떤 집합의 '부분'이 되는 집합이다.
  Ex) {1, 2, 3}의 부분 집합은 공집합, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이 있다.

👉🏻 멱집합 구하기

⇒ 멱집합은 해당 집합의 모든 부분 집합을 모은 것이다. 따라서, 해당 집합의 원소가 총 N개라고 한다면 0부터 N개의 원소를 가지는 모든 부분 집합을 구하면 멱집합을 구할 수 있다.
따라서, 기본적으로 원소의 수를 바꿔 가면서 모든 조합을 구해주면 멱집합을 쉽게 구할 수 있다.

// {1, 2, 3} 의 부분 집합 구하기

import java.util.Arrays;

public class Ex_Subset {
	
	static int target, totalCnt = 0;
	
	static int[] dice = {1,2,3};
	
	static int[] numbers;
	
	public static void main(String[] args) {
		for(int i = 0; i<= dice.length; i++) {
			numbers = new int[i];
			
			target = i;

			subSet(0, 0);
		}
		
		System.out.println("부분 집합의 수 : "+totalCnt);

	}
	
	static void subSet(int start, int cnt) {
		if(target == cnt) {
			totalCnt++;
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for(int i = start; i < dice.length ; i++) {
			numbers[cnt] = dice[i];
			subSet(i+1, cnt+1);
		}
	}

}