Table of contents
순열
정의
서로 다른 nn개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 nn개에서 rr개를 택하는 순열이라고 한다
순열은 순서를 중요하게 여긴다. 다섯 명의 사람(A, B, C, D, E)이 있고, 이들을 각각 다른 의자에 앉힌다고 하자. 5개의 의자(C1, C2, C3, C4, C5)가 필요하다. 만약, 사람들을 순서대로 앉힌다면 C1에는 다섯명이 앉을 수 있다고 말하거나 다섯명 모두 C1 의자에 앉을 수 있다고 말할 수 있다. 동시에 각각의 경우에 대해, C1에 이미 한명이 앉아있는 상태이므로 C2에는 네명이 앉을 수 있다.
이를 경우의 수로 말하자면 동시에 일어나는 사건이므로 5 * 4 = 20 가 된다. 다시 각 20가지 경우에 대해 C3에는 몇 명이 앉을 수 있을까? 5명 중 2명이 이미 앉은 상태로, 3명이 남아있기 때문에 C3에는 3명이 앉을 수 있다. 이는 각 20가지 경우에서 동시에 3가지씩의 경우가 추가됨을 의미한다. 예를들어 AB가 앉은 상태라면 ABC, ABD, ABE가 될 수 있으며, AC가 앉은 상태라면 ACB, ACD, ACE가 될 수 있다. 즉, 첫 세사람을 앉히는 경우의 수는 5 * 4 * 3이 된다. 마지막 C5까지 진행하여 결과는 5 * 4 * 3 * 2 * 1 = 120이 된다. 이는 **n!**를 의미한다.
공식
nPr = n! / (n - r)!
이번에는 조금 더 깊게 들어가서 다섯 명의 사람은 그대로 있지만, 의자가 3개(C1, C2, C3)만 있다고 가정해보자. 단, 어떤 의자에 누가 앉는지를 고려해야 한다고 가정한다(순서가 중요하다). 앞의 과정과 마찬가지로 진행하지만, C3 의자까지만 진행한다. C1에서 5명, C2에서 4명, 마지막 C3에서 3명을 뽑는다. 결과는 5 * 4 * 3 = 60이 된다.
방금 푼 문제(5 * 4 * 3)는 5!에서 2 * 1만 빠진 형태다. 5 * 4 * 3 * 2 * 1에서 2 * 1로 나누어주면 5 * 4 * 3이 된다. 이제 5!/2!라고 쓸 수 있다. 여기서 2!는 어디서 나온 것일까? 의자는 3개인데 2가 나온것에 의문을 품을 수도 있겠다. 잘 생각해보면 의자의 개수만큼만 곱하기를 하고 그 이후로는 곱하지 않았음을 알 수 있다. 결국, 곱하기를 하지 않은 부분은 (사람의 수 - 의자의 개수)가 된다. 다섯 명의 사람을 세 개의 의자에 앉히려고 하는데, (5 - 3) = 2명이 남는다.
정리하자면, 5명의 사람 중 3명을 뽑으면 2명이 남는다. 5명의 사람은 n, 뽑으려고 하는 3명은 r 그리고 남는 2명은 (n - r) 이 된다.
다시 한번 강조하지만 순열은 순서를 중요시 여겨 같은 조합이라도 순서가 다르다면 별개로 취급한다. 순열에서 AB와 BA는 엄연히 다르다.
구현
private void permutation(int[] arr, int depth, int n, int r) {
if (depth == r) {
for (int i = 0; i < r; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
return;
}
for (int i = depth; i < n; i++) {
swap(arr, depth, i);
permutation(arr, depth + 1, n, r);
swap(arr, depth, i);
}
}
순열에 대한 구현은 간단하다. 바로 이해하기는 힘들 수도 있는데, 그런 경우 직접 그리면서 디버깅을 해보자.
출처: http://www.eandbsoftware.org/print-all-permutations-of-a-given-string/
사전순 순열
순열을 사전순으로 정렬해서 출력하는 방법은 여러 가지가 있다. 순열을 구한 뒤 정렬하는 방법도 있고, 아래처럼 순환쉬프트를 이용하는 방법도 있다.
private void permutation(int[] arr, int depth, int n, int r) {
if (depth == r) {
for (int i = 0; i < r; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
return;
return;
}
for (int i = depth; i < n; i++) {
rotateToRight(arr, depth, i);
permutation(arr, depth + 1, n, r);
rotateToLeft(arr, depth, i);
}
}
private void rotateToRight(int[] arr, int start, int end) {
int last = arr[end];
for (int i = end; i > start; i--) {
arr[i] = arr[i - 1];
}
arr[start] = last;
}
private void rotateToLeft(int[] arr, int start, int end) {
int first = arr[start];
for (int i = start; i < end; i++ ) {
arr[i] = arr[i + 1];
}
arr[end] = first;
}
직접 그리면서 따라가다 보면 기본 순열과는 달리 사전순으로 진행되는 것을 알 수 있다. 이전에는 CBA가 CAB보다 먼저 출력되었지만, 사전순으로 CAB가 먼저이므로 swap이 아닌 순환쉬프트를 사용한다.
조합
정의
서로 다른 nn개의 원소에서 순서에 상관없이 rr개를 뽑을 때, 이를 nn개에서 rr개를 택하는 조합이라고 한다. 이 조합은 순열과 다른 개념으로 순서 차이가 중요하다.
조합은 순서를 중요하지 않게 여긴다. 다시 여러 명의 사람들이 특정 수의 의자에 앉을 수 있는 방법에 대해 생각해보자. 여섯 명의 사람(A, B, C, D, E, F)이 있고, 이들을 각각 3개의 의자(C1, C2, C3)에 앉힌다고 하자.
3개의 의자에 않히는 모든 상황
C1부터 시작한다. 처음 6명의 다른 사람들은 C1에 앉을 수 있다. C1에 앉는 6개의 경우가 생긴다. 다시 각 6개의 경우마다 한 사람이 의자 1에 않아 있으니 C2에 사람이 앉는 경우 5가지가 추가되어 2명이 C2과 C2에 앉아있는 경우, 총 30가지의 경우가 된다. 의자 3개에 대해서는 어떨까? 각 30개의 경우마다 4명의 사람이 앉을 수 있다. 그래서 누가 어떤 의자에 앉는지 생각했을 때의 경우의 수는 6 * 5 * 4 = 120개의 순열이 된다.
공식
nCr = n! / (n - r)! r!
순열이라는 것이 무엇을 세는지에 대해 생각해 보자. 순열이라고 하면 위의 문제에서 어떤 사람이 어떤 의자에 앉는지가 중요하다. ABC가 하나의 순열이고 ACB, BAC, BCA, CAB, CBA도 각각 하나의 순열이라고 말한다. 이 순열들을 보면 모두 똑같이 A, B와 C가 앉아있지만 각 순열에서 사람들은 다른 의자에 앉아 있다.
- ABC BAC CAB ACB BCA CBA
- FBC BFC CFB FCB BCF CBF
- ..... 6개의 순열이 총 5개
위의 순열은 단순히 120개 중에 12개다. 하지만, 의자에 앉을 3명을 어떤 의자인지 상관하지 않고 고른다면 이러한 것들은 모두 하나의 경우가 된다.
그렇다면 6명의 사람들을 3개의 의자에 앉힐 때 의자에 상관없이 3명을 앉히는 경우는 몇 가지가 될까?
- ABC BAC CAB ACB BCA CBA
- ABC를 뽑는 순열을 나열하는 방법 = 6가지
- FBC BFC CFB FCB BCF CBF
- BCF를 뽑는 순열을 나열하는 방법 = 6가지
3명의 사람들을 나열할 때 6가지의 다른 방법으로 나열할 수 있다. 자세히 살펴보면 이 각각의 묶음이 하나의 조합이라는 것을 알 수 있다. A, B, C 라는 사람들이 어떤 순서로 앉던 상관 없이 6명 중에 3명을 뽑은 묶음이다. 사람들의 조합을 고르는 거니까 순서는 상관없다. 여기 있는 F, C, B 조합도 또 다른 하나의 조합이다.
전체 순열에서, 이처럼 3명의 사람을 나열한 수를 나누면 120/6 = 20조합이 된다. 정리하자면, 6명의 사람 중 3명을 뽑으면 3명이 남는다. 6명의 사람은 n, 뽑으려고 하는 3명은 r 그리고 남는 3명은 (n - r)이 되며 이는 순열 nPr = 6 * 5 * 4 = 120이다. 조합은 여기서 뽑은 3명의 사람을 다시 나열한 r! = 3! = 3 * 2 * 1 = 6 만큼은 중복이 되므로 해당 중복만큼 나눠서 nCr = 120 / 6 = 20이 된다.
조합이라는 의미를 잘 생각해보자. ABC, ACB, BAC, BCA, CAB, CBA는 모두 A, B, C 세 개의 요소로 이루어진 같은 조합이다.
구현
private void combination(int[] arr, int n, int r) {
int[] data = new int[n];
combination2(arr, new int[r], 0, 0, n, r);
}
private void combination(int[] arr, int[] data, int start, int depth, int n, int r) {
if (depth == r) {
for (int j = 0; j < r; j++) {
System.out.print(data[j] + " ");
}
System.out.println();
return;
}
for (int i = start; i < n; i++) {
data[depth] = arr[i];
combination(arr, data, i + 1, depth + 1, n, r);
}
}
depth에 요소를 고정시켜가면서 start부터 반복하여 조합을 탐색한다. {1, 2, 3, 4, 5}에서 4개의 조합을 구한다면 123을 고정하고 start가 4를 탐색하여 1234, 5를 탐색하여 1235를 출력한 뒤 다시 3을 고정하기 전으로 돌아간다. 이번에는 124를 고정하고 start가 5를 탐색하여 1245를 출력한다. 이러한 고정, 탐색, 출력을 반복한다.
private void combination(int[] arr, int n, int r) {
combination(arr, new int[n], n, r, 0, 0);
}
private void combination(int[] arr, int[] data, int n, int r, int index, int target) {
if (r == 0) {
for (int j = 0; j < index; j++) {
System.out.print(data[j] + " ");
}
System.out.println();
return;
} else if (target == n) {
return;
} else {
data[index] = arr[target];
combination(arr, data, n, r - 1, index + 1, target + 1);
combination(arr, data, n, r, index, target + 1);
}
}
재귀만을 이용하는 구현법도 있다. 각 요소에 대해 뽑은 경우와 뽑지 않은 경우를 고려한다. 요소를 하나씩 뽑을때마다 r이 감소된다. r이 0이 되면 원하는 개수만큼 다 뽑았다는 의미이므로 출력한다. 반대로 target은 요소를 뽑지 않아도 1씩 증가한다. target이 n이 된다는 의미는 아직 원하는 개수만큼 다 뽑지 않았지만, 모든 요소를 탐색했음을 의미하여 더 이상 진행하지 않는다. index는 뽑은 요소가 들어갈 위치에 해당하는 변수이다.