1. 순열 (Permutation)
서로 다른 n개의 원소 중에서 r개를 중복 없이 골라 순서에 상관있게 나열하는 경우의 수 (nPr)
예제) [A, B, C, D, E]로 이뤄진 5장의 카드가 있을 때, 이 5장의 카드 중 3장을 선택하여 나열하려고 한다. 이때, 순서를 생각하며 3장을 선택하는 모든 경우의 수를 나열하시오.
5P3 = 5! / (5-3)! = 5*4*3 = 60
🔽 for loop로 구현
function permutationLoop(list) {
const result = [];
for (let i = 0; i < list.length; i++) {
for (let j = 0; j < list.length; j++) {
for (let k = 0; k < list.length; k++) {
// 중복된 요소 제거
if (i === j || j === k || k === i) continue;
result.push([list[i], list[j], list[k]]);
}
}
}
return result;
}
permutationLoop(["A", "B", "C", "D", "E"])// 결과값
[
[ 'A', 'B', 'C' ], [ 'A', 'B', 'D' ], [ 'A', 'B', 'E' ],
[ 'A', 'C', 'B' ], [ 'A', 'C', 'D' ], [ 'A', 'C', 'E' ],
[ 'A', 'D', 'B' ], [ 'A', 'D', 'C' ], [ 'A', 'D', 'E' ],
[ 'A', 'E', 'B' ], [ 'A', 'E', 'C' ], [ 'A', 'E', 'D' ],
[ 'B', 'A', 'C' ], [ 'B', 'A', 'D' ], [ 'B', 'A', 'E' ],
[ 'B', 'C', 'A' ], [ 'B', 'C', 'D' ], [ 'B', 'C', 'E' ],
[ 'B', 'D', 'A' ], [ 'B', 'D', 'C' ], [ 'B', 'D', 'E' ],
[ 'B', 'E', 'A' ], [ 'B', 'E', 'C' ], [ 'B', 'E', 'D' ],
[ 'C', 'A', 'B' ], [ 'C', 'A', 'D' ], [ 'C', 'A', 'E' ],
[ 'C', 'B', 'A' ], [ 'C', 'B', 'D' ], [ 'C', 'B', 'E' ],
[ 'C', 'D', 'A' ], [ 'C', 'D', 'B' ], [ 'C', 'D', 'E' ],
[ 'C', 'E', 'A' ], [ 'C', 'E', 'B' ], [ 'C', 'E', 'D' ],
[ 'D', 'A', 'B' ], [ 'D', 'A', 'C' ], [ 'D', 'A', 'E' ],
[ 'D', 'B', 'A' ], [ 'D', 'B', 'C' ], [ 'D', 'B', 'E' ],
[ 'D', 'C', 'A' ], [ 'D', 'C', 'B' ], [ 'D', 'C', 'E' ],
[ 'D', 'E', 'A' ], [ 'D', 'E', 'B' ], [ 'D', 'E', 'C' ],
[ 'E', 'A', 'B' ], [ 'E', 'A', 'C' ], [ 'E', 'A', 'D' ],
[ 'E', 'B', 'A' ], [ 'E', 'B', 'C' ], [ 'E', 'B', 'D' ],
[ 'E', 'C', 'A' ], [ 'E', 'C', 'B' ], [ 'E', 'C', 'D' ],
[ 'E', 'D', 'A' ], [ 'E', 'D', 'B' ], [ 'E', 'D', 'C' ]
]5개 중 3개를 뽑는 경우이기 때문에 3중 중첩 for문을 작성했다. 4개를 뽑거나 5개를 뽑는 경우의 수를 구하려면 4중, 5중 for문을 써야 하기 때문에 for loop hell이 열리기 딱 좋다. 무엇보다 뽑아야 되는 개수를 변수로 받는 함수를 작성하기가 어렵다. 하지만 재귀 함수를 사용해서 풀면 선택할 수 있는 대상이 되는 요소와 선택 개수를 변수로 받을 수 있다.
🔽 재귀로 구현
i번째 자리에 선택할 수 있는 아이템들을 for 문으로 탐색하는데, 현재 i번째 아이템을 제외한 나머지 아이템으로 배열을 재구성해서 재귀의 매개변수(rest)로 전달해준다. 선택된 아이템(items)의 개수가 선택하고자 하는 아이템의 개수와 동일할 경우 재귀를 종료한다.
function permutationRecursive(list, choiceNum) {
const result = [];
// 내부함수 : filter나 splice로 중복 제거
function helper(items, rest) {
if (items.length === choiceNum) { // base condition
result.push(items);
return;
}
for (let i = 0; i < rest.length; i++) {
// 1. splice 메소드로 rest 배열 만들기
const temp = rest.slice();
temp.splice(i, 1);
// 2. filter 메소드로 rest 배열 만들기
// const temp = rest.filter((el, idx) => idx !== i);
helper([...items, rest[i]], temp);
}
}
helper([], list);
return result;
}
permutationRecursive(["A", "B", "C", "D", "E"], 3);
또다른 방법으로는 원본 배열인 list의 요소의 위치를 swap해주며 경우의 수를 구하는 방법도 있다. 다만 swap을 하면서 원본 배열의 인덱스를 swap하기 때문에 결과값은 담는 result 배열에 알파벳 순 정렬이 되지 않는다. 알파벳 순서라 함은 A와 D를 먼저 뽑고 마지막 세 번째 카드를 뽑을 때 [ 'A', 'D', 'B' ], [ 'A', 'D', 'C' ], [ 'A', 'D', 'E' ] 순서가 아닌 [ 'A', 'D', 'C' ], [ 'A', 'D', 'B' ], [ 'A', 'D', 'E' ] 순서로 결과가 담기기 때문에 문제에서 정렬된 결과를 원하는 경우 사용할 수 없다.
function permutationRecursive(list, choiceNum) {
const result = [];
// 내부함수 : swapping으로 중복 제거
function helper(i) {
if (i === choiceNum) {
result.push(list.slice(0, i));
return;
}
for (let j = i; j < list.length; j++) {
[list[i], list[j]] = [list[j], list[i]];
helper(i + 1);
// 재귀 호출이 한 턴 종료가 되면 원본 배열을 다시 원래의 자리로 되돌린다.
[list[j], list[i]] = [list[i], list[j]];
}
}
helper(0);
return result;
}
2. 조합 (Combination)
서로 다른 n개의 원소 중에서 r개를 중복 없이 골라 순서에 상관없게 나열하는 경우의 수 (nPr)
위의 순열과 똑같은 예제를 조합으로 바꿔보자.
[A, B, C, D, E]로 이뤄진 5장의 카드가 있을 때, 이 5장의 카드 중 3장을 선택하여 나열하려고 한다. 이때, 순서에 상관 없이 3장을 선택하는 모든 경우의 수를 나열하시오.
5C3 = 5! / (5-3)! * 3! = 5*4/2*1 = 10
🔽 for loop로 구현
순열에는 [A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A] 의 여섯 가지가 모두 다른 경우이지만, 조합에서는 이 여섯 가지를 하나의 경우로 취급한다. 따라서 조합에서는 한 번 조합한 요소는 다시 조합하지 않는 것이 핵심이다. 하나의 요소로 만들 수 있는 경우의 수를 전부 다 구한 다음, 그 요소를 반복에 포함하지 않고 그 다음 요소부터 시작할 수 있게 반복문을 돌리면 된다.
function combinationLoop(list) {
const result = [];
for (let i = 0; i < list.length; i++) {
// i번째 요소로 조합할 수 있는 경우를 다 찾은 이후에는
// i번째 요소를 포함하지 않기 위해 그 다음 요소(i+1)부터 반복문을 시작한다.
for (let j = i + 1; j < list.length; j++) {
for (let k = j + 1; k < list.length; k++) {
result.push([list[i], list[j], list[k]]);
}
}
}
return result;
}
combinationLoop(["A", "B", "C", "D", "E"])// 결과값
[
[ 'A', 'B', 'C' ],
[ 'A', 'B', 'D' ],
[ 'A', 'B', 'E' ],
[ 'A', 'C', 'D' ],
[ 'A', 'C', 'E' ],
[ 'A', 'D', 'E' ],
[ 'B', 'C', 'D' ],
[ 'B', 'C', 'E' ],
[ 'B', 'D', 'E' ],
[ 'C', 'D', 'E' ]
]
🔽 재귀로 구현
기본 로직은 순열과 동일하다. 현재 선택한 i번째 아이템 다음의 아이템을 다음 재귀의 매개변수로 전달해 주면 되기 때문에 현재 인덱스의 다음 순서인 i+1을 재귀의 매개변수로 전달한다.
function combinationRecursion(list, choiceNum) {
const result = [];
function helper(items, index) {
if (items.length === choiceNum) {
result.push(items);
return;
}
for (let i = index; i < list.length; i++) {
helper([...items, list[i]], i + 1);
}
}
helper([], 0);
return result;
}
3. 중복 순열 (Permutation with repetition)
서로 다른 n개의 원소 중에서 r개를 중복을 허용하며 골라 순서에 상관있게 나열하는 경우의 수 (n^r)
중복 순열과 중복 조합은 동일한 아이템을 2회 이상 선택할 수 있기 때문에 [A, B, C, D, E] 중에서 3개를 선택하는 경우 [A, A, A]가 허용된다. 중복 순열은 처음에 n개를 선택하고, 그 다음에 또 n개를 선택할 수 있기 때문에 총 경우의 수가 n^r이 된다.
🔽 for loop로 구현
for문으로 구현하는 경우 앞서 순열을 for loop로 구현한 코드에서 중복 요소를 제거해주는 라인만 제거하면 간단하게 구현할 수 있다.
function pwrLoop(list) {
const result = [];
for (let i = 0; i < list.length; i++) {
for (let j = 0; j < list.length; j++) {
for (let k = 0; k < list.length; k++) {
result.push([list[i], list[j], list[k]]);
}
}
}
return result;
}
pwrLoop(["A", "B", "C", "D", "E"]) // 총 125(5**3)가지 경우의 수
🔽 재귀로 구현
i+1번째에 추가할 아이템의 범위를 정할 때 i번째 아이템도 포함한다. 0부터 i-1까지 이전에 선택했던 모든 아이템들을 범위에 포함해야 하기 때문에 재귀 함수(helper) 내에서 for문을 전체 범위로 설정한다.
function pwrRecursion(list, choiceNum) {
const result = [];
function helper(items) {
if (items.length === choiceNum) {
result.push(items);
return;
}
for (let i = 0; i < list.length; i++) {
helper([...items, list[i]]);
}
}
helper([]);
return result;
}
4. 중복 조합 (Combination with repetition)
서로 다른 n개의 원소 중에서 r개를 중복을 허용하며 골라 순서에 상관 없게 나열하는 경우의 수 (nHr = n+r-1Cr)
🔽 for loop로 구현
중복 순열과 마찬가지로 i+1번째에 추가할 아이템의 범위를 정할 때 i번째 아이템도 포함해야 하기 때문에 i+1번째가 아닌 i번째부터 반복문을 시작한다.
function cwrLoop(list) {
const result = [];
for (let i = 0; i < list.length; i++) {
for (let j = i; j < list.length; j++) {
for (let k = j; k < list.length; k++) {
result.push([list[i], list[j], list[k]]);
}
}
}
return result;
}
cwrLoop(["A", "B", "C", "D", "E"]) // 총 35가지 경우의 수// 결과값
[
[ 'A', 'A', 'A' ], [ 'A', 'A', 'B' ],
[ 'A', 'A', 'C' ], [ 'A', 'A', 'D' ],
[ 'A', 'A', 'E' ], [ 'A', 'B', 'B' ],
[ 'A', 'B', 'C' ], [ 'A', 'B', 'D' ],
[ 'A', 'B', 'E' ], [ 'A', 'C', 'C' ],
[ 'A', 'C', 'D' ], [ 'A', 'C', 'E' ],
[ 'A', 'D', 'D' ], [ 'A', 'D', 'E' ],
[ 'A', 'E', 'E' ], [ 'B', 'B', 'B' ],
[ 'B', 'B', 'C' ], [ 'B', 'B', 'D' ],
[ 'B', 'B', 'E' ], [ 'B', 'C', 'C' ],
[ 'B', 'C', 'D' ], [ 'B', 'C', 'E' ],
[ 'B', 'D', 'D' ], [ 'B', 'D', 'E' ],
[ 'B', 'E', 'E' ], [ 'C', 'C', 'C' ],
[ 'C', 'C', 'D' ], [ 'C', 'C', 'E' ],
[ 'C', 'D', 'D' ], [ 'C', 'D', 'E' ],
[ 'C', 'E', 'E' ], [ 'D', 'D', 'D' ],
[ 'D', 'D', 'E' ], [ 'D', 'E', 'E' ],
[ 'E', 'E', 'E' ]
]
🔽 재귀로 구현
중복 순열은 i+1번째 아이템을 선택할 때 전체 아이템을 선택하지만, 중복 조합은 이전에 선택했던 아이템들은 제외해야 하기 때문에 재귀 함수(helper) 내에서 for 문의 범위를 현재 인덱스 i로 설정해주면 된다.
function cwrRecursion(list, choiceNum) {
const result = [];
function helper(items, index) {
if (items.length === choiceNum) {
result.push(items);
return;
}
for (let i = index; i < list.length; i++) {
helper([...items, list[i]], i);
}
}
helper([], 0);
return result;
}
📚 참고자료
[javascript] 순열, 조합, 중복순열, 중복조합
순열, 조합
jjnooys.medium.com
'배워서 남 주자' 카테고리의 다른 글
| [TWIL] 사전 프로젝트를 하며 알게 된 몇 가지 - 1편 (0) | 2023.02.25 |
|---|---|
| eslint, prettier 설정 파일 세팅 (0) | 2023.02.19 |
| axios로 CRUD 요청하기 (0) | 2023.02.07 |
| 배열 초기화: Array.fill()과 Array.from()의 차이 (0) | 2023.02.06 |
| to do 앱 만들면서 새로 알게 된 css 몇 가지 - 2편 (0) | 2023.02.05 |