JavaScript_순열과 조합
순열
순열(順列, permutation)은 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것이며, 이는 조합과 마찬가지로 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다.
위 3개의 원소로는 총 6개의 부분집합이 나올 수 있다
순열의 식은 이렇게 표현된다.
n은 원소의 총 개수를 의미하고, r은 그중 뽑는 개수를 의미한다.
조합
조합(組合, combination)은 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관없게 r개의 원소를 선택하는 것이며, 이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다.
3개의 원소로 이루어진 집합이 있다. 
이는 총 3개의 부분집합이 나올 수 있다. 왜냐하면 조합은 순서에 상관없이 원소를 선택해 부분집합을 만드는 것이기 때문이다.
조합의 식은 이렇게 표현한다.
여기서 n은 원소의 총 개수를 의미하고, r은 그중 뽑는 개수를 의미한다. 여기서 중요한 것은, 앞서 설명했듯이 조합은 중복을 허용하지 않기 때문에 반드시 R ≤ N을 만족해야 한다는 것이다.
이렇게 식을 통해 확인해 보았을 때도 3개의 부분조합이 도출이 됨을 알 수 있다.
순열과 조합 - 순열과 조합을 이용한 문제
문제: 카드 뽑기
[A, B, C, D, E]로 이뤄진 5장의 카드가 있습니다. 이 5장의 카드 중 3장을 선택하여 나열하려고 합니다. 이때, 다음의 조건을 각각 만족하는 경우를 찾아야 합니다.
- 순서를 생각하며 3장을 선택합니다.
- 순서를 생각하지 않고 3장을 선택합니다.
각 조건을 만족시키며 카드를 나열하는 방법은 각각 몇 가지일까요?
case 1. 순서를 생각하며 3장을 선택할 때의 모든 경우의 수
- 첫번째 나열하는 카드를 선택하는 방법에는 다섯 가지가 있다.
- 첫번째 카드를 나열하고 난 다음, 두번째 카드를 선택하는 방법에는 네 가지가 있다.
- 두번째 카드를 나열하고 난 다음, 세번째 카드를 선택하는 방법에는 세 가지가 있다.
따라서 5 X 4 X 3 = 60 가지의 방법이 있다.
이렇게 n 개 중에서 일부만을 선택하여 나열하는 것을 순열이라고 한다. 순열은 순서를 지키며 나열해야 한다.
- 3장을 선택하는 모든 순열의 수 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60
- 일반식 : nPr = n! / (n - r)!
반복문 코드
function permutationLoop() {
// 순열 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
// 문제 안에 포함되어 있을 경우 이런 식으로 직접 적어서 사용합니다.
let lookup = ['A', 'B', 'C', 'D', 'E'];
let result = [];
for (let i = 0; i < lookup.length; i++) {
for (let j = 0; j < lookup.length; j++) {
for (let k = 0; k < lookup.length; k++) {
if(i === j || j === k || k === i) continue;
result.push([lookup[i], lookup[j], lookup[k]])
}
}
}
return result;
}
permutationLoop();
result 배열 안에 순열의 경우의 수를 삽입한 뒤, 반환하는 함수이다
Awsome 코드
const getCombinations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((el) => [el]);
// n개중에서 1개 선택할 때(nC1), 바로 모든 배열의 원소 return
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1);
// 해당하는 fixed를 제외한 나머지 뒤
const combinations = getCombinations(rest, selectNumber - 1);
// 나머지에 대해서 조합을 구한다.
const attached = combinations.map((el) => [fixed, ...el]);
// 돌아온 조합에 떼 놓은(fixed) 값 붙이기
results.push(...attached);
// 배열 spread syntax 로 모두다 push
});
return results; // 결과 담긴 results return
}case 2. 순서를 생각하지 않고 3장을 선택할 때의 모든 경우의 수
2번 조건에서 모든 경우의 수를 구할 때는 3장을 하나의 그룹으로 선택해야 한다.
다음과 같은 방법으로 경우의 수를 구한다.
- 순열로 구할 수 있는 경우를 찾는다.
- 순열로 구할 수 있는 경우에서 중복된 경우의 수를 나눈다.
- 5장에서 3장을 무작위로 선택하는 조합에서 모든 경우의 수 = 5C3 = 5! / (3! * 2!) = 10
- 일반식: nCr = n! / (r! * (n - r)!)
반복문 코드
function combinationLoop() {
// 조합 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
// 문제 안에 포함되어 있을 경우 이런 식으로 직접 적어서 사용합니다.
let lookup = ['A', 'B', 'C', 'D', 'E'];
let result = [];
console.log(lookup);
for (let i = 0; i < lookup.length; i++) {
for (let j = i + 1; j < lookup.length; j++) {
for (let k = j + 1; k < lookup.length; k++) {
result.push([lookup[i], lookup[j], lookup[k]]);
}
}
}
return result;
}
combinationLoop();순열과 다른 점은, 반복의 조건에 있다. (i = 0, j = i + 1, k = j + 1)
한 번 조합한 요소는 다시 조합하지 않는다.
Awsome 코드
const getPermutations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((el) => [el]);
// n개중에서 1개 선택할 때(nP1), 바로 모든 배열의 원소 return. 1개선택이므로 순서가 의미없음.
arr.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
// 해당하는 fixed를 제외한 나머지 배열
const permutations = getPermutations(rest, selectNumber - 1);
// 나머지에 대해서 순열을 구한다.
const attached = permutations.map((el) => [fixed, ...el]);
// 돌아온 순열에 떼 놓은(fixed) 값 붙이기
results.push(...attached);
// 배열 spread syntax 로 모두다 push
});
return results; // 결과 담긴 results return
}