🌼 순열과 조합
경우의 수를 구할 때 사용되는 수학 이론이다. 서로 다른 n개의 원소 중에서 r개를 뽑아 나열하는 방법의 수를 nPr이라고 표현하며 이를 순열(비복원 추출)이라고 한다. 원소를 뽑고 이를 원소에 포함하여 원소를 뽑고 나열하는 경우에 이를 nΠr이라고 표현하며 중복 순열(복원 추출)이라고 한다.
nPr 공식: n x (n - 1) x .... x (n - (r - 1)) = n! / (n - r)!
nPr = {n x (n - 1) x .... x (n - r + 1) x (n - r) x .... 2 x 1} / {(n - r) x .... 2 x 1}
= n! / (n - r)!nΠr 공식: n^r
서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 방법의 수를 nCr이라고 표현하며 이를 조합이라고 한다. 원소를 뽑고 이를 원소에 포함하여 다시 뽑는 경우에 이를 nHr이라고 표현하며 중복 조합이라고 한다.
-
nCr 공식: nPr / r! = n! / {(n - r)! x r!}, nPr 공식에서 순서가 다른 조합의 경우를 없애준다. -
nHr 공식: {(n - 1) + r}Cr, 중복으로 원소를 선택하기 위한 경계선(n - 1)과 빈 자리에 원소(r)를 선택할 조합의 수를 구한다. 여기서 경계선은 r개를 뽑을 때 n개를 어떤 형태로 중복할지를 구분하는 경계선을 말한다.
순열(Permutation)과 조합(Combination)의 차이는 다음과 같다.
-
순서 여부: 순열은 순서가 있고 조합은 순서가 없다. -
표현 방법: 순열은 배열하는 방법이 정해져 있지 않아 선택과 배열의 과정이 필요하나 조합은 배열하는 방법이 한가지로 정해져 있어 선택의 과정만 필요하다. -
동일 판단: 순열은 손서가 있기 때문에 {a, b} != {b, a}이지만 조합은 순서가 없어 {a, b} == {b, a}로 판단한다.
순열과 조합 외에 중복 순열과 중복 조합도 있는데 여기서 중복의 개념은 경우의 수를 생성할 때 이미 선택된 값도 선택의 대상이 될 수 있다는 개념으로 이해할 수 있다.
🌼 알고리즘 구현
재귀를 사용하여 알고리즘을 구현할 수 있다. 구현시 내가 하나를 선택했을 때 그 다음에 선택할 수 있는 경우의 묶음(restArr)을 구성하는 것이 가장 중요하다.
let arr = ['A', 'B', 'C'];
let digits = 2;
// 1.순열
function permutation(arr, digits) {
let answer = new Array();
if (digits == 1) return arr.map((_) => [_]);
arr.forEach((e, idx, arr) => {
let pick = e;
let restArr = arr.filter((_, index) => index !== idx); // <- attention!
let permutationArr = permutation(restArr, digits -1);
let mergedElement = permutationArr.map((j) => [pick, ...j].join(''));
answer.push(...mergedElement);
});
return answer;
}
// 2. 중복 순열
function duplicatePermutation(arr, digits) {
let answer = new Array();
if (digits == 1) return arr.map((_) => [_]);
arr.forEach((e, idx, arr) => {
let pick = e;
let restArr = arr; // <- attention!
let permutationArr = duplicatePermutation(restArr, digits - 1);
let mergedElement = permutationArr.map((j) => [pick, ...j].join(''));
answer.push(...mergedElement);
});
return answer;
}
// 3. 조합
function combination(arr, digits) {
let answer = new Array();
if (digits == 1) return arr.map((_) => [_]);
arr.forEach((e, idx, arr) => {
let pick = e;
let restArr = arr.slice(idx + 1); // <- attention!
let combinationArr = combination(restArr, digits - 1);
let mergedElement = combinationArr.map((j) => [pick, ...j].join(''));
answer.push(...mergedElement);
});
return answer;
}
// 4. 중복 조합
function combination(arr, digits) {
let answer = new Array();
if (digits == 1) return arr.map((_) => [_]);
arr.forEach((e, idx, arr) => {
let pick = e;
let restArr = arr.slice(idx); // <- attention!
let combinationArr = combination(restArr, digits - 1);
let mergedElement = combinationArr.map((j) => [pick, ...j].join(''));
answer.push(...mergedElement);
});
return answer;
} 출처: 순열과 조합
