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

개념 정리

순열 (P : Permutation)

순서가 있음 : 금고의 각 자리 비밀번호는 순서가 있다!

keyword : 서로 다른, 나열하다

 

A와 B, B와 A는 서로 다른 것이다. (비밀번호 486과 468은 서로 다른 비밀번호이다.)

 

수학 공식 : 

$_nP_r = \frac{n!}{(n-r)!}$

$_4P_2 = \frac{4!}{(4-2)!} = \frac{4 * 3 * 2 * 1}{2* 1}=12$

 

 

조합 (C : Combination)

순서가 없음 : 콤비네이션 피자는 여러 재료의 조합으로 된 피자이다! (재료의 순서가 없음)

keyword : 동시에 꺼내다, 선택하다

 

A와 B, B와 A는 같은 것으로 취급함

 

수학 공식 :

$_nC_r = \frac{_nP_r}{r!}=\frac{n!}{(n-r)! * r!}$

$_4C_2 = \frac{_4P_2}{r!}=\frac{4!}{(4-2)! * 2!} =\frac{4!}{2! * 2!}=\frac{4*3*2*1}{2 * 2}=6$

 

 

중복 순열, 중복 조합

순열과, 조합에 각각 중복 가능한 경우를 더함

-> [1, 1, 2] 등 하나의 숫자에 대하여 여러 번 나타나는 경우

 

 

부분 집합 

N개의 숫자 중 0~N개를 선택하는 경우를 구하는 것

= 조합의 집합

 

 

코드

순열

public class 순열 {
	public static void main(String[] args) {
		int[] arr = { 1, 3, 5 };
		recursive(arr, new int[2], new boolean[arr.length], 0);
	}

	/*
	 * arr[] : 원본 배열 | sel[] : 담는 배열 | v[] : 사용 여부 | sIdx : 담는 배열 인덱스
	 */
	private static void recursive(int[] arr, int[] sel, boolean[] v, int sIdx) {
		// basis part
		if (sIdx == sel.length) {
			System.out.println(Arrays.toString(sel));
			return;
		}

		// inductive part
		for (int i = 0; i < arr.length; i++) {
			if (v[i] == false) {
				v[i] = true;
				sel[sIdx] = arr[i];
				recursive(arr, sel, v, sIdx + 1);
				v[i] = false; // 백트레킹, 다른 마디 탐색을 위해서
			}
		}

	}
}

 

- 결과

 

[1, 3]

[1, 5]

[3, 1]

[3, 5]

[5, 1]

[5, 3]

 

 

 

중복 순열

public class 중복순열 {
	public static void main(String[] args) {
		int[] arr = { 1, 3, 5 };
		recursive(arr, new int[2], 0);
	}

	/*
	 * arr[] : 원본 배열 | sel[] : 담는 배열 | sIdx : 담는 배열 인덱스
	 */
	private static void recursive(int[] arr, int[] sel, int sIdx) {
		// basis part
		if (sIdx == sel.length) {
			System.out.println(Arrays.toString(sel));
			return;
		}

		// inductive part
		for (int i = 0; i < arr.length; i++) {
			sel[sIdx] = arr[i];
			recursive(arr, sel, sIdx + 1);
		}
	}
}

 

- 결과

 

[1, 1]

[1, 3]

[1, 5]

[3, 1]

[3, 3]

[3, 5]

[5, 1]

[5, 3]

[5, 5]

 

 

 

조합

public class 조합 {
	public static void main(String[] args) {
		int[] arr = { 1, 3, 5 };
		recursive(arr, new int[2], 0, 0);
	}

    /*
     * arr[] : 원본 배열 | sel[] : 선택 배열 | aIdx : 원본 배열 인덱스 | sIdx : 선택 배열 인덱스
     */
	private static void recursive(int[] arr, int[] sel, int aIdx, int sIdx) {
		// basis part
		if (sIdx == sel.length) {
			System.out.println(Arrays.toString(sel));
			return;
		}
		
		// inductive part
		for (int i = aIdx; i < arr.length; i++) {
			sel[sIdx] = arr[i];
			recursive(arr, sel, i + 1, sIdx + 1); // aIdx가 아니라 i 값을 전달함!!
		}
	}
}

 

- 결과

 

[1, 3]

[1, 5]

[3, 5]

 

 

 

 

중복 조합

public class 중복조합 {
	public static void main(String[] args) {
		int[] arr = { 1, 3, 5 };
		recursive(arr, new int[2], 0, 0);
	}

	/*
	 * arr[] : 원본 배열 | sel[] : 선택 배열 | aIdx : 원본 배열 인덱스 | sIdx : 선택 배열 인덱스
	 */
	private static void recursive(int[] arr, int[] sel, int aIdx, int sIdx) {
		// basis part
		if (sIdx == sel.length) {
			System.out.println(Arrays.toString(sel));
			return;
		}

		// inductive part
		for (int i = aIdx; i < arr.length; i++) {
			sel[sIdx] = arr[i];
			recursive(arr, sel, i, sIdx + 1); // aIdx가 아니라 i 값을 전달함!!
		}
	}
}

 

- 결과

 

[1, 1]

[1, 3]

[1, 5]

[3, 3]

[3, 5]

[5, 5]

 

 

 

부분 집합

public class 부분집합 {
	public static void main(String[] args) {
		int[] arr = { 1, 3, 5 };
		recursive(arr, new boolean[arr.length], 0);
	}

	/*
	 * arr[] : 원본 배열 | v[] : 선택 배열 | aIdx : 원본 배열 인덱스
	 */
	private static void recursive(int[] arr, boolean[] v, int aIdx) {
		// basis part
		if (aIdx == arr.length) {
			for (int i = 0; i < v.length; i++) {
				if(v[i]) {
					System.out.print(arr[i] + " ");
				} else {
					// System.out.print("false : " + arr[i] + " ");
				}
			}
			System.out.println();
			return;
			
		}
		
		// inductive part
		v[aIdx] = true;
		recursive(arr, v, aIdx + 1);
		v[aIdx] = false;
		recursive(arr, v, aIdx + 1);
		
	}
}

 

- 결과

 

1 3 5

1 3

1 5

1

3 5

3

5

 

 

 

정리

방문 확인은 순열, 부분 집합만 사용함 

부분 집합은 for문 대신 2번 재귀 호출

순열은 백트래킹을 가짐

 

순열 -> 중복 순열 : 방문 확인 제거

조합 -> 중복 조합 : 재귀 시 i 값을 증가하지 않음

 

 

 

순한맛 순조부

암기가 어렵다면 전역으로 바꾼 순한 버전 순열 / 조합 / 부분집합을 확인하세요.

 

- 순열

public class new순열 {
	static int[] arr;
	static boolean[] v;
	static int[] sel;
	static int size;
	static int answer;
	
	public static void main(String[] args) {
		arr = new int[] { 1, 3, 5 };
		size = 2; // 3P2
		v = new boolean[arr.length];
		sel = new int[size];
		answer = 0;
		
		recursive(0);
		System.out.println(answer);
	}

	private static void recursive(int count) {
		if (count == size) {
			answer ++;
			System.out.println(Arrays.toString(sel));
			return;
		}
		
		for (int i = 0; i < arr.length; i++) {
			if(v[i]) continue; // 방문 했으면
			v[i] = true;
			sel[count] = arr[i];
			recursive(count + 1);
			sel[count] = 0;
			v[i] = false;
 		}
	}
}

 

 

- 중복 순열

순열과 단 한줄 차이!

public class new중복순열 {
	static int[] arr;
	static boolean[] v;
	static int[] sel;
	static int size;
	static int answer;

	public static void main(String[] args) {
		arr = new int[] { 1, 3, 5 };
		size = 2;
		v = new boolean[arr.length];
		sel = new int[size];
		answer = 0;

		recursive(0);
		System.out.println(answer);
	}

	private static void recursive(int count) {
		if (count == size) {
			answer++;
			System.out.println(Arrays.toString(sel));
			return;
		}

		for (int i = 0; i < arr.length; i++) {
//			if(v[i]) continue; // 들어왔던 것이 다시 들어올 수 있으면 중복 순열
			v[i] = true;
			sel[count] = arr[i];
			recursive(count + 1);
			sel[count] = 0;
			v[i] = false;
		}

	}
}

 

 

- 조합

순열에서

1)start 변수 추가

2)for문이 바뀌면

조합

public class new조합 {
	static int[] arr;
//	static boolean[] v;
	static int[] sel;
	static int size;
	static int answer;

	public static void main(String[] args) {
		arr = new int[] { 1, 3, 5 };
		size = 2; //
//		v = new boolean[arr.length];
		sel = new int[size];
		answer = 0;

		recursive(0, 0);
		System.out.println(answer);
	}

	private static void recursive(int count, int start) { // 시작점 변수 추가
		if (count == size) {
			answer++;
			System.out.println(Arrays.toString(sel));
			return;
		}

		for (int i = start; i < arr.length; i++) { // 순열에서 for문이 바뀌면 조합!
//			v[i] = true;
			sel[count] = arr[i];
			recursive(count + 1, i + 1);
			sel[count] = 0;
//			v[i] = false;
		}

	}
}

 

 

 

- 중복 조합

조합에서 재귀 호출 부분에 start를 증가시키지 않으면 중복 조합

import java.util.Arrays;

public class new중복조합 {
	static int[] arr;
//	static boolean[] v;
	static int[] sel;
	static int size;
	static int answer;

	public static void main(String[] args) {
		arr = new int[] { 1, 3, 5 };
		size = 2; //
//		v = new boolean[arr.length];
		sel = new int[size];
		answer = 0;

		recursive(0, 0);
		System.out.println(answer);
	}

	private static void recursive(int count, int start) {
		if (count == size) {
			answer++;
			System.out.println(Arrays.toString(sel));
			return;
		}

		for (int i = start; i < arr.length; i++) {
//			v[i] = true;
			sel[count] = arr[i];
			recursive(count + 1, i); // i + 1 -> i
			sel[count] = 0;
//			v[i] = false;
		}

	}
}

 

 

- 부분집합

순열에서

1) for문을 날리고,

2) 재귀를 한 번 더 돌리면 부분 집합

import java.util.Arrays;

public class new부분집합 {
	static int[] arr;
	static boolean[] v;
//	static int[] sel;
	static int size;
	static int answer;

	public static void main(String[] args) {
		arr = new int[] { 1, 3, 5 };
		size = 2;
		v = new boolean[arr.length];
//		sel = new int[size];
		answer = 0;

		recursive(0);
		System.out.println(answer);
	}

	private static void recursive(int count) {
		if (count == arr.length) { // 모든 숫자에 대해서 선택해봤는가 여부 확인
			answer++;
			System.out.println(Arrays.toString(v));
			return;
		}

//		for (int i = 0; i < arr.length; i++) {
//			if(v[i]) continue; // 방문 했으면
			v[count] = true;
//			sel[count] = arr[i];
			recursive(count + 1); // 넣을 경우
//			sel[count] = 0;
			v[count] = false;
			recursive(count + 1); // 안넣을 경우

// 		}

	}
}