순열과 조합을 직접 구현하며 작동원리를 이해하고 기록한다.
순열
// 순열
function Permutation(arr, r) {
const result = [];
if (r === 1) return arr.map((num) => [num]);
arr.forEach((fixed, index, org) => {
const rest = [...org.slice(0, index), ...org.slice(index + 1)];
const permutation = Permutation(rest, r - 1);
const attached = permutation.map((numbers) => [fixed, ...numbers]);
result.push(...attached);
});
return result;
}
//전체 순열
function GetAllPermutation (arr){
const results=[];
arr.forEach((value,index,origin)=>{
results.push(...Permutation(origin,index+1));
});
return results;
}
조합
function Combination(arr, r) {
const result = [];
if (r === 1) return arr.map((num) => [num]);
arr.forEach((fixed, index, org) => {
const rest = org.slice(index+1);
const combinations = Combination(rest, r - 1);
const attached = combinations.map((numbers) => [fixed, ...numbers]);
result.push(...attached);
});
return result;
}
'코딩테스트(알고리즘) > 알고리즘 구현' 카테고리의 다른 글
[알고리즘 구현] 소수 찾기, 에라토스테네스의 체 (Javascript) (0) | 2022.06.25 |
---|---|
[알고리즘 구현] 이진탐색 binarySearch (Javascript) (0) | 2022.06.25 |
[알고리즘 구현] 정렬 sort (Javascript) (0) | 2022.06.25 |
BFS 구현 (C++) (0) | 2022.06.17 |
코딩테스트 대비 자료구조 Javascript 구현 (0) | 2022.06.13 |