[Java] 조합 (Combination)과 순열(Permutation)

'모든 경우의 수를 구하시오'(완전탐색)에 대한 문제에서 가장 많이 등장하는 알고리즘이다. 

조합 (Combination)

조합 nCr은 n개의 값 중에서 r개의 값을 순서를 고려하지 않고 뽑는 것이다.

간혹 문제와 함께보면 어떤걸 써야하는지 헷갈리는데 필자의 경우 주며니에 담는다라고 생각하면 이해가 빠르다고 느꼈다. 주머니에 공을 넣은 후 주머니의 상태는 공을 어느 순서로 넣었는지는 중요하지 않다.

아래 예시로 조합을 백트래킹과 재귀로 구현하는 법을 알아보겠다.

조합 구현 

public class Combination {

	public static void main(String[] args) {
		int[] arr = { 1, 9, 5, 4, 3 };
		int n = 5;
		int r = 3;

		System.out.println("1. 백트랙킹");
		combi1(arr, new int[r], new boolean[n], n, r, 0, 0);

		System.out.println("2. 재귀");
		combi2(arr, new int[r], new boolean[n], n, r, 0, 0);
	}

	//1. 백트랙킹
	/* arr: 길이 n의 int 배열, 여기서 숫자를 뽑는다
	*  output: 길이 r의 int 배열, 뽑은 조합을 이 곳에 저장한다
	*  visited: 길이 n의 boolean 배열, 이 위치에 있는 arr이 이미 뽑혔는지 저장한다
	*  n: arr의 길이, 전체 값의 수
	*  r: ouput의 길이, 뽑을 값의 수 (고정)
	*  start: 어느 위치부터 수를 뽑을지 정하는 index 값
	*  depth: 현재 뽑힌 수의 수
	*/
	public static void combi1(int[] arr, int[] output, boolean[] visited, int n, int r, int start, int depth) {
		if (depth == r) {
			printArr(output);
			return;
		}

		for (int i = start; i < n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				output[depth] = arr[i];
				combi1(arr, output, visited, n, r, i + 1, depth + 1);
				visited[i] = false;
			}
		}
	}

	//2. 재귀
	/* arr: 길이 n의 int 배열, 여기서 숫자를 뽑는다
	*  output: 길이 r의 int 배열, 뽑은 조합을 이 곳에 저장한다
	*  visited: 길이 n의 boolean 배열, 이 위치에 있는 arr이 이미 뽑혔는지 저장한다
	*  n: arr의 길이, 전체 값의 수
	*  r: 앞으로 뽑아야할 수 (가변)
	*  index: 현재 뽑힌 수의 수, output 어디에 넣을 차례인지 알려주는 index 값
	*  depth: arr의 어느 위치까지 확인했는지 알려주는 index 값
	*/
	public static void combi2(int[] arr, int[] output, boolean[] visited, int n, int r, int index, int depth) {
		if (r == 0) {
			printArr(output);
			return;
		}
		if (depth == n) {
			return;
		}

		visited[depth] = true;
		output[index] = arr[depth];
		combi2(arr, output, visited, n, r - 1, index + 1, depth + 1);

		visited[depth] = false;
		combi2(arr, output, visited, n, r, index, depth + 1);
	}

	public static void printArr(int[] print) {
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		for (int p : print) {
			sb.append(p);
			sb.append(" ");
		}
		sb.setLength(sb.length() - 1);
		sb.append("]");

		System.out.println(sb.toString());
	}
}

 

순열 (Permutation)

순열 nPr은 n개의 값 중에서 r개의 값을 순서를 고려해서 뽑는 것이다.

순열을 생각할 때는 사전을 떠올리는 편이다. abc로 만들 수 있는 모든 글자를 뽑는다는 생각을하면 된다.

순열 또한 백트래킹으로 문제를 푸는 방법이 있고 swap 함수를 이용하여 문제를 푸는 방법이 있다. swap을 사용하는 방식은 아래의 그림을 참고해보면 쉽게 이해가 가능할 것이다.

 

public class Permutation {

	public static void main(String[] args) {
		int[] arr = { 1, 9, 5, 4, 3 };
		int n = 5;
		int r = 3;

		System.out.println("1. 백트랙킹");
		permu1(arr, new int[r], new boolean[n], n, r, 0);

		System.out.println("2. swap");
		permu2(arr, n, r, 0);
	}

	//1. 백트랙킹
	/* arr: 길이 n의 int 배열, 여기서 숫자를 뽑는다
	 * n: arr의 길이, 전체 값의 수
	 * r: ouput의 길이, 뽑을 값의 수 (고정)
	 * depth: 현재 뽑힌 수의 수
	 * visited: 길이 n의 boolean 배열, 이 위치에 있는 arr이 이미 뽑혔는지 저장한다
	 * output: 길이 r의 int 배열, 뽑은 조합을 이 곳에 저장한다
	 */
	// 조합과 차이점: 조합은 이미 확인한 항목 이전의 항목은 확인하지 않는다. (각 항목이 뽑혔거나, 말았거나 둘 중 하나고 한번 결정됐으면 그 뒤로 바뀌지 않는다. 순열은 이 자리에 넣지 않았다고 하더라도 (당시에 뽑히지 않았다고 하더라도) 나중에 다른 자리에는 넣을 수도 있다 (나중에 뽑히는 경우). 그렇기 때문에 start없이 depth만 보고 무조건 처음부터 끝까지 확인한다.
	public static void permu1(int[] arr, int[] output, boolean[] visited, int n, int r, int depth) {
		if (depth == r) {
			printArr(output);
			return;
		}

		for (int i = 0; i < n; i++) {
			if (visited[i] != true) {
				visited[i] = true;
				output[depth] = arr[i];
				permu1(arr, output, visited, n + 1, r, depth + 1);
				visited[i] = false;
			}
		}
	}

	//2. swap
	/* arr: 길이 n의 int 배열, 여기서 숫자를 뽑는다
	 * n: arr의 길이, 전체 값의 수
	 * r: ouput의 길이, 뽑을 값의 수 (고정)
	 * depth: 현재 뽑힌 수의 수
	 * visited: 길이 n의 boolean 배열, 이 위치에 있는 arr이 이미 뽑혔는지 저장한다
	 */
	static void permu2(int[] arr, int n, int r, int depth) {
		if (depth == r) {
			printArr(arr);
			return;
		}

		for (int i = depth; i < n; i++) {
			swap(arr, depth, i);
			permu2(arr, depth + 1, n, r);
			swap(arr, depth, i);
		}
	}

	static void swap(int[] arr, int depth, int i) {
		int temp = arr[depth];
		arr[depth] = arr[i];
		arr[i] = temp;
	}

	public static void printArr(int[] print) {
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		for (int p : print) {
			sb.append(p);
			sb.append(" ");
		}
		sb.setLength(sb.length() - 1);
		sb.append("]");

		System.out.println(sb.toString());
	}
}