[알고리즘] 순열, 중복순열, 조합, 중복 조합, 부분집합

• 주사위 던지기

package algorithm_live.day02.pcs;

import java.util.Arrays;
import java.util.Scanner;

public class DiceTest {
	static int N, numbers[], totalCnt;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		numbers = new int[N];
		
		int M =sc.nextInt();
		
		switch (M) {
		case 1:
			dice1(0);
			break;
		case 2:
			dice2(0,new boolean[7]);
			break;
		case 3:
			dice3(0,1);
			break;
		case 4:
			dice4(0,1);
			break;

		default:
			break;
		}
		
		System.out.println("총 경우의 수: "+totalCnt);
		
	}
	
	//주사위 던지기 1: 중복순열
	public static void dice1(int cnt) {
		if(cnt==N){
			totalCnt++;
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for(int i=1;i<=6;i++) {	//i=주사위의 눈
			numbers[cnt]=i;
			dice1(cnt+1);
		}
	}
	
	//주사위 던지기 2: 순열 nPr
	public static void dice2(int cnt, boolean[] isSelected) {
		
		if(cnt==N) {
			totalCnt++;
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for(int i=1;i<=6;i++) {
			if(isSelected[i]) continue;
			
			numbers[cnt]=i;
			isSelected[i]=true;
			
			dice2(cnt+1,isSelected);
			isSelected[i]=false;
		}
	}
	
	//주사위 던지기 3: 중복 조합 nHr=n+r+1Cr
	public 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);	//다음 주사위는 선택한 현재 수부터 시도.
		}
	}
	
	//주사위 던지기 4: 조합 nCr
	public 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);	//다음 주사위는 선택한 현재 수의 다음 수부터 시도.
		}
	}
	
}

• 부분 집합

package algorithm_live.day02.pcs;

import java.util.Scanner;

public class SubSetTest {
	static int N,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);
	}
	
	public static void generateSubset(int cnt) {	//부분집합에 고려해야 하는 원소, 직전까지 고려한 원소 수
		
		if(cnt==N) {	//마지막 원소까지 부분집합에 다 고려된 상황
			
			for(int i=0;i<N;i++) {
				System.out.print((isSelected[i]?input[i]:"X")+" ");
			}
			System.out.println();
			
			return;
		}
		
		//현재 원소를 선택
		isSelected[cnt] =true;
		generateSubset(cnt+1);
		//현재 원소를 비선택
		isSelected[cnt]=false;
		generateSubset(cnt+1);
	}
}