[Java]순열(Permutation)

*순열(Permutation)

-> 순열이란, 임의의 집합을 순서를 부여하여 차례로 나열하는 것을 말한다.

Ex) 이를 테면 집합 {1, 2, 3}중 3개의 원소를 선택한 순열을 구하시오라고 하면, 결과는 {123, 132, 213, 231, 312, 321} 총 6가지의 경우의 수가 나온다.

순열 경우의 수

※ 순열이 총 6가지가 나오는 이유는, 위의 예시에서 선택한 3가지 수를 위 박스에 하나씩 넣는 상황을 가정해보면, 첫 번째 자리에는 {1, 2, 3}중 한 가지 숫자 어느것이든 올 수 있다. 두 번째 자리에는 앞에서 이미 한 가지 수를 선택했으므로, 그 선택한 수를 제외한 2가지 숫자가 어느 것이든 올 수 있다. 마지막 자리는 선택이 되지 않은 나머지 한 가지 수가 오게 될 것이다. 따라서 3개의 숫자를 3개선택한 순열의 경우의수는 총 6가지이다.

-> 위의 순열의 경우의 수를 일반화하면, n개의 수 중 r개를 선택하는 순열은 총 n!/(n - r)!개의 경우의수를 가짐을 알 수 있다(수학적으로 여러가지 방법으로 표현 가능하다).

순열 경우의 수

*구현(Java)

-> 로직은 위에 언급한 예시를 그대로 구현했다고 생각하면 된다. 따라서, 순열은 재귀를 이용하면 쉽게 구현할 수 있다. 

※ 순열 알고리즘

1. 대상 집합을 순회하며 숫자를 하나 선택하는 것을 아래와 같이 반복한다.

(1) 만일, 숫자가 이미 선택되었다면 그 숫자는 선택할 수 없으므로 스킵한다.

(2) 만일, 숫자가 선택되지 않았다면 그 숫자에 대하여 방문 표시를하고 자신의 메서드를 재귀 호출한다.

2. 선택된 숫자가 r개가 된다면, 재귀를 종료한다.

 

-> 예를 들어, 1부터 3까지의 자연수 3개중 2개를 선택한 순열을 다음과 같이 구현할 수 있다.

public class Permutation {
	// 선택하고자 하는 대상 집합.
	static int[] target = new int[] { 1, 2, 3 };
	// 대상 숫자를 선택했는지를 알려주는 집합.
	static boolean[] visited = new boolean[3];

	public static void main(String[] args) {
		permutation(0, "");
	}

	// 순열 메서드(cnt는 선택 횟수, result는 결과)
	private static void permutation(int cnt, String result) {
		// 2개를 선택했으므로, 결과를 출력하고 재귀를 종료한다.
		if (cnt == 2) {
			System.out.println(result);
			return;
		}
		// 대상 집합을 순회하며 숫자를 하나 선택한다.
		for (int i = 0; i < 3; i++) {
			// 이미 해당 숫자를 선택한 경우에는 스킵.
			if (visited[i]) {
				continue;
			}
			// 선택하지 않은경우, 선택했다는 표시를 해준다.
			visited[i] = true;
			// 자신을 재귀 호출한다.
			permutation(cnt + 1, result + target[i]);
			// 선택을 해제한다.
			visited[i] = false;
		}
	}
}

-> 다음과 같이, 매개변수를 1개만 사용하여 만들수도 있다. 위의 예시와 같이 상자라는 대상을 더욱 구체화 시킨 것이라고 볼 수 있다. 매개변수의 수보다는, 순열을 구현하는 로직을 정확히 이해하도록 하자.

import java.util.Arrays;

public class Permutation {
	// 선택하고자 하는 대상 집합.
	static int[] target = new int[] { 1, 2, 3 };
	// 대상 숫자를 선택했는지를 알려주는 집합.
	static boolean[] visited = new boolean[3];
	// 대상 숫자를 담아둘 배열을 만든다.
	static int[] result = new int[2];

	public static void main(String[] args) {
		permutation(0);
	}

	// 순열 메서드(cnt는 선택 횟수)
	private static void permutation(int cnt) {
		// 2개를 선택했으므로, 결과를 출력하고 재귀를 종료한다.
		if (cnt == 2) {
			System.out.println(Arrays.toString(result));
			return;
		}
		// 대상 집합을 순회하며 숫자를 하나 선택한다.
		for (int i = 0; i < 3; i++) {
			// 이미 해당 숫자를 선택한 경우에는 스킵.
			if (visited[i]) {
				continue;
			}
			// 선택하지 않은경우, 선택했다는 표시를 해준다.
			visited[i] = true;
			// 숫자를 담는다.
			result[cnt] = target[i];
			// 자신을 재귀 호출한다.
			permutation(cnt + 1);
			// 선택을 해제한다.
			visited[i] = false;
		}
	}
}