November 3, 2021
Intro: [이투스 한컷강의 수학 정승제선생님] 조합과 순열은 어떻게 다를까? (feat. 조합의 정의)
<aside> 💡 7C3 = 7P3 / 3! (조합을 구하려면 순열을 구해서 팩토리얼을 나누어준다)
</aside>
https://jun-choi-4928.medium.com/javascript로-순열과-조합-알고리즘-구현하기-21df4b536349
const getCombinations = function(arr, selectNumber) {
const results = [];
if(selectNumber === 1) return arr.map((value) => [value]);
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1);
const combinations = getCombinations(rest, selectNumber - 1);
const attached = combinations.map((combination) => [fixed, ...combination]);
results.push(...attached);
})
return results;
}
const getCombinations = function(arr, selectNumber) {
//! selectNumber는 몇 개의 숫자를 뽑을 것이냐.
const results = [];
if(selectNumber === 1) return arr.map((value) => [value]);
// 하나만 선택한다고 했을 때
// arr 배열의 모든 값들이 1, 2, 3, 4 이렇게 있으면 각각 [ ] 배열로 감싸서
// [[1], [2], [3], [4]] 이렇게 바꿔주는 작업.
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1);
// 나머지(rest) 는 origin 배열에서 index를 제외한 나머지값을 의미한다.
const combinations = getCombinations(rest, selectNumber - 1);
// 맨 앞 fixed는 '무조건' 포함 되어야하므로, fixed를 제외한 나머지 숫자들을 재귀함수로 보내준다.
// 예를들어 [1, 2, 3, 4] 에서 3개 숫자를 뽑는다고 한다면
// [1, 2, 3], [1, 2, 4], [1, 3, 4] 등
// 1은 무조건 뽑고 나머지 [2, 3, 4] 에서 2개를 더 뽑아야 하는 것이므로
// 현재 fixed인 1을 제외한 나머지와 3개 숫자 뽑는다 -> 2개 숫자 뽑는다 로 바꿔서 보내준다.
const attached = combinations.map((combination) => [fixed, ...combination]);
// 1을 제외한 배열의 모든 index들([2, 3, 4]) 에 대해서도 똑같이 진행한다... 만...
// 어차피 바로 [2, 3, 4] 배열이 나온 뒤 selectNumber가 1이 될 것이므로 재귀는 끝이 난다.
results.push(...attached);
// 전개연산자를 통해 '깊은 복사' 를 해서 results에 넣어주고, 그것을 return 한다.
})
return results;
}
const example = [1,2,3,4];
const result = getCombinations(example, 3);
console.log(result);
//[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
이번에는 나를 제외한 배열의 모든 원소에 대해서 순열을 구하는 함수에 일을 위임하면 된다. 아래의 코드를 살펴보면 정확히 다른 코드는 동일하고 배열의 나머지를 구하는 코드만 바뀌었음을 볼 수 있다.
const rest = [...origin.slice(0, index), ...origin.slice(index+1)] // 해당하는 fixed를 제외한 나머지 배열
unction getPermutations(arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((v) => [v]);
else {
arr.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
const permutations = getPermutations(rest, selectNumber - 1);
const attached = permutations.map((permutation) => [
fixed,
...permutation,
]);
results.push(...attached);
});
}
return results;
}
const getPermutations= function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return
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((permutation) => [fixed, ...permutation]); // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
results.push(...attached); // 배열 spread syntax 로 모두다 push
});
return results; // 결과 담긴 results return
};
const example = [1,2,3,4];
const result = getPermutations(example, 3);
console.log(result);
// => [
// [ 1, 2, 3 ], [ 1, 2, 4 ],
// [ 1, 3, 2 ], [ 1, 3, 4 ],
// [ 1, 4, 2 ], [ 1, 4, 3 ],
// [ 2, 1, 3 ], [ 2, 1, 4 ],
// [ 2, 3, 1 ], [ 2, 3, 4 ],
// [ 2, 4, 1 ], [ 2, 4, 3 ],
// [ 3, 1, 2 ], [ 3, 1, 4 ],
// [ 3, 2, 1 ], [ 3, 2, 4 ],
// [ 3, 4, 1 ], [ 3, 4, 2 ],
// [ 4, 1, 2 ], [ 4, 1, 3 ],
// [ 4, 2, 1 ], [ 4, 2, 3 ],
// [ 4, 3, 1 ], [ 4, 3, 2 ]
// ]