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

직관적으로 예시를 드는것이 이해하기 쉬워서 주사위 던지는 것을 예시로 든다.

---

중복 순열

- 주사위 3개를 던져 나올 수 있는 모든 경우의 수

- 123, 231은 다른 경우로 본다. 즉, 뽑는 순서가 상관이 있다.

- 112처럼 같은 수를 중복으로 뽑을 수 있다.

- n개 중 r개를 뽑는 모든 경우의 수를 nπr로 표현한다.

코드

결과

111, 112, 113, ~, 211, 212, ~ 666

---

순열

- 주사위 3개를 던져 모두 다른 수가 나올 수 있는 경우의 수

- 123, 231은 다른 경우로 본다. 즉, 뽑는 순서가 상관이 있다.

- 112처럼 같은 수를 중복으로 뽑을 수 없다.

- n개 중 r개를 중복되지 않게 뽑는 모든 경우의 수를 nPr로 표현한다.

코드

결과

123, 124, 125, ~, 213, 214, ~, 654

---

중복 조합

- 주사위 3개를 던져 나올 수 있는 경우의 수로, 순서를 따지지 않는다.

- 123, 231은 같은 경우로 본다. 즉, 뽑는 순서가 상관이 없다.

- 112처럼 같은 수를 중복으로 뽑을 수 있다.

- n개 중 r개를 순서를 따지지 않고 뽑는 모든 경우의 수를 nHr로 표현한다.

코드

결과

111, 112, 113, ~, 222, 223, ~, 666

---

조합

- 주사위 3개를 던져 모두 다른 수가 나올 수 있는 경우의 수로, 순서를 따지지 않는다.

- 123, 231은 같은 경우로 본다. 즉, 뽑는 순서가 상관이 없다.

- 112처럼 같은 수를 중복으로 뽑을 수 없다.

- n개 중 r개를 순서를 따지지 않고 중복되지 않게 뽑는 모든 경우의 수를 nCr로 표현한다.

코드

결과

123, 124, ~, 234, 235, ~, 456

---

전체코드

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

public class DiceTest {

	static int N, numbers[];
	static boolean[] isSelected;

	public static void main(String[] args) {

		// 입력으로 주사위 던지는 횟수, 주사위 던지기 모드(1, 2, 3, 4)
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // 주사위 던지는 횟수(0 < N < 7)
		int M = sc.nextInt(); // 주사위 던지기 모드
		numbers = new int[N]; // 던져진 주사위 수들
		switch (M) {
		case 1: // 중복순열
			dice1(0);
			break;
		case 2: // 순열
			isSelected = new boolean[7]; // 주사위 0번 사용x
			dice2(0);
			break;
		case 3: // 중복조합
			dice3(0, 1);
			break;
		case 4: // 조합 6C2 = 6! / 2! * 4! = 15가지
			dice4(0, 1);
			break;
		}
		sc.close();
	}

	// 중복 순열
	static void dice1(int cnt) { // cnt + 1번째 주사위 던지기, cnt: 기존까지 던져진 주사위 횟수

		if (cnt == N) { // N번을 다 던진 경우
			System.out.println(Arrays.toString(numbers));
			return;
		}

		// 한 번 던질 때 가능한 상황에 대한 시도(1, 2, 3, 4, 5, 6 주사위 눈이 가능)
		for (int i = 1; i <= 6; i++) {
			numbers[cnt] = i;
			// 현 주사위의 눈이 i로 결정된 상태로 다음 주사위 던지러 가기
			dice1(cnt + 1);
		}
	}

	// 순열
	static void dice2(int cnt) { // cnt + 1번째 주사위 던지기, cnt: 기존까지 던져진 주사위 횟수

		if (cnt == N) { // N번을 다 던진 경우
			System.out.println(Arrays.toString(numbers));
			return;
		}

		// 한 번 던질 때 가능한 상황에 대한 시도(1, 2, 3, 4, 5, 6 주사위 눈이 가능)
		for (int i = 1; i <= 6; i++) {
			// 기존 주사위의 눈과 중복되는지 체크
			if (isSelected[i])
				continue;
			numbers[cnt] = i;
			isSelected[i] = true;
			// 현 주사위의 눈이 i로 결정된 상태로 다음 주사위 던지러 가기
			dice2(cnt + 1);
			// 현 주사위의 눈을 다른 선택지로 시도하기 위한 준비
			isSelected[i] = false;
		}
	}

	// 중복조합
	static void dice3(int cnt, int start) { // start: 시작 주사위 눈의 수

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

		for (int i = start; i <= 6; i++) {
			numbers[cnt] = i;
			dice3(cnt + 1, i); // i: 뽑는 수
		}
	}

	// 조합
	static void dice4(int cnt, int start) { // start: 시작 주사위 눈의 수

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

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