[#17] 순열 & 조합 & 부분집합

순열

• 순서를 고려하여 원소를 나열하는 방법
• 같은 원소라도 순서가 다르면 다른 경우로 취급
• ex) 집합 {1, 2, 3}에서 2개를 선택하는 순열: (1,2), (1,3), (2,1), (2,3), (3,1), (3,2) ➡️ 총 6가지
• 주사위 문제

package 순조부;

import java.util.Arrays;

public class 주사위_일반순열 {
	static int[] result;
	static boolean[] isSelected;
	static int n;
	static int totalCnt; // 재귀를 돈 횟수
	
	public static void main(String[] args) {
		n = 2; // 주사위 던지는 횟수
		result = new int[n];
		isSelected = new boolean[7];

		주사위던지기(0);
		System.out.println(totalCnt);

	}

	private static void 주사위던지기(int cnt) { // cnt는 판의 횟수
		if (cnt == n) {
			totalCnt++;
			System.out.println(Arrays.toString(result));
			return;
		}

		for (int i = 1; i <= 6; i++) {
			if (isSelected[i]) continue; // 중복 선택 방지
			result[cnt] = i; // 주사위 던진 결과 저장
			isSelected[i] = true;
			주사위던지기(cnt + 1);
			isSelected[i] = false; // 다시 돌아가는 시점에 선택 유무 배열 초기화
		}

	}

}

조합

• 순서를 고려하지 않고 원소를 선택하는 방법
• 같은 원소를 뽑더라도 순서가 다르면 같은 경우로 취급
• ex) 집합 {1, 2, 3}에서 2개를 선택하는 조합: {1,2}, {1,3}, {2,3} ➡️ 총 3가지
• 주사위 문제

package 순조부;

import java.util.Arrays;

public class 주사위_일반조합 {
	static int[] result;
	static int n;
	static int totalCnt;
	
	public static void main(String[] args) {
		n = 2;
		result = new int[n];
		
		주사위던지기(0, 1); // 두 번째 인수는 순서와 중복을 없애기 위해 주사위의 가장 작은 숫자 1을 부여
		System.out.println(totalCnt);
	
	}

	private static void 주사위던지기(int cnt, int start) {
		if(cnt == n) {
			totalCnt++;
			System.out.println(Arrays.toString(result));
			return;
		}
		
		for (int i = start; i <= 6; i++) {
			result[cnt] = i;
			주사위던지기(cnt + 1, i + 1); // 그 다음 판은 뽑은 i 값 보다 1 큰 수를 전달 
		}
		
	}

}

부분집합

• 주어진 집합에서 원소를 선택하거나 선택하지 않는 모든 경우를 포함하는 개념
• 순서를 고려하지 않음
• ex) 집합 {1, 2, 3}의 모든 부분집합: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} ➡️ 총 2^3 = 8가지
• 주사위 문제

package 순조부;

public class 주사위_부분집합 {
	static boolean[] isSelected;
	static int[] input = { 1, 2, 3, 4, 5, 6 };
	static int totalCnt;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		long startTime = System.nanoTime();
		
		isSelected = new boolean[6]; // 6개 숫자에 대한 선택 여부를 저장할 배열

		subset(0);
		System.out.println(sb);
		System.out.println(totalCnt);
		
		long endTime = System.nanoTime();
		System.out.println(endTime - startTime);
	}

	private static void subset(int cnt) {

		if (cnt == 6) {
			totalCnt++; // 완성된 하나의 부분집합 개수 연산
			// 현재 완성된 부분집합 출력
			for (int i = 0; i < 6; i++) {
				// System.out.print(isSelected[i] ? input[i] : "X");
				sb.append(isSelected[i] ? input[i] : "X");
			}
			// System.out.println();
			sb.append("\n");
			return;

		}

		// 현재 원소를 선택하는 경우
		isSelected[cnt] = true;
		subset(cnt + 1); // 다음 원소로 진행

		// 현재 원소를 선택하지 않는 경우
		isSelected[cnt] = false;
		subset(cnt + 1);

	}

}

 

💡 수업 미션: 순열 & 조합 & 부분집합에 대한 문제 정의

순열 Q) 1부터 N까지의 숫자가 적힌 N장의 카드가 있을 때, 이 카드들을 한 줄로 나열하는 모든 순열 출력하기 (N = 3)

package 순조부;

import java.util.Arrays;

public class 카드_일반순열 {
	static int[] result;
	static boolean[] isSelected;
	static int n;

	public static void main(String[] args) {
		n = 3;
		result = new int[n];
		isSelected = new boolean[n + 1];

		카드뽑기(0);

	}

	private static void 카드뽑기(int cnt) {
		if (cnt == n) {
			System.out.println(Arrays.toString(result));
			return;
		}

		for (int i = 1; i <= 3; i++) {
			if (isSelected[i]) continue;
			result[cnt] = i;
			isSelected[i] = true;
			카드뽑기(cnt + 1);
			isSelected[i] = false;

		}

	}

}

➡️ 출력

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 1, 2]

[3, 2, 1]

 

조합 Q) 한 피자 가게에서 N가지 토핑 중에서 원하는 토핑을 골라 피자를 만들 수 있을 때, 고객이 최소 1개 이상 M개 이하의 토핑을 선택할 수 있는 가능한 모든 조합을 출력하기 (N = 4, M = 2)

package 순조부;

import java.util.Arrays;

public class 피자토핑_일반조합 {
	static String[] topping = { "Pepperoni", "Mushroom", "Olive", "Cheese" };
	static int n;

	public static void main(String[] args) {
		n = topping.length;

		for (int m = 1; m <= 2; m++) {
			토핑선택(new String[m], 0, 0, m);
		}

	}

	private static void 토핑선택(String[] result, int cnt, int start, int m) {
		if (cnt == m) {
			System.out.println(Arrays.toString(result));
			return;
		}

		for (int i = start; i < topping.length; i++) {
			result[cnt] = topping[i];
			토핑선택(result, cnt + 1, i + 1, m);
		}

	}

}

➡️ 출력

• 1가지 이상 M가지 이하의 가능한 모든 토핑 출력

[Pepperoni]

[Mushroom]

[Olive]

[Cheese]

[Pepperoni, Mushroom]

[Pepperoni, Olive]

[Pepperoni, Cheese]

[Mushroom, Olive]

[Mushroom, Cheese]

[Olive, Cheese]

 

부분집합 Q) 주어진 친구 목록에서 일부 친구들을 초대할 수 있을 때, 친구를 초대하지 않는 경우도 포함하여 가능한 모든 초대 목록 구하기

package 순조부;

import java.util.*;

public class 친구목록_부분집합 {
	static String[] friends = { "짱구", "철수", "유리", "훈이", "맹구" };
	static boolean[] isSelected;
	static StringBuilder sb = new StringBuilder();
	static List<String> subsets = new ArrayList<>();

	public static void main(String[] args) {
		isSelected = new boolean[friends.length];
		subset(0);

		// 리스트 길이 순으로 정렬
		subsets.sort(Comparator.comparingInt(String::length));

		// 정렬된 결과 출력
		for (String subset : subsets) {
			sb.append(subset).append("\n");
		}

		System.out.println(sb);
	}

	private static void subset(int cnt) {
		if (cnt == friends.length) {
			StringBuilder currentSubset = new StringBuilder();
			for (int i = 0; i < friends.length; i++) {
				if (isSelected[i]) {
					currentSubset.append(friends[i]).append(" ");
				}
			}
			
			// 초대한 친구가 없는 경우 "X" 출력
			if(currentSubset.length() <= 0) {
				currentSubset.append("X");
			}
			
			// currentSubset에 쌓인 내용을 String 형태로 subsets 리스트에 추가
			subsets.add(currentSubset.toString());
			return;
		}

		// 현재 친구를 초대하는 경우
		isSelected[cnt] = true;
		subset(cnt + 1);

		// 현재 친구를 초대하지 않는 경우
		isSelected[cnt] = false;
		subset(cnt + 1);
	}
}

➡️ 출력

X

짱구

철수

유리

훈이

맹구

짱구 철수

짱구 유리

짱구 훈이

짱구 맹구

철수 유리

철수 훈이

철수 맹구

유리 훈이

유리 맹구

훈이 맹구

짱구 철수 유리

짱구 철수 훈이

짱구 철수 맹구

짱구 유리 훈이

짱구 유리 맹구

짱구 훈이 맹구

철수 유리 훈이

철수 유리 맹구

철수 훈이 맹구

유리 훈이 맹구

짱구 철수 유리 훈이

짱구 철수 유리 맹구

짱구 철수 훈이 맹구

짱구 유리 훈이 맹구

철수 유리 훈이 맹구

짱구 철수 유리 훈이 맹구