알고리즘 문제들을 풀다보면 순열과 조합을 이용해 문제를 해결하는 경우가 있다. 기존에는 알고리즘 문제들을 파이썬을 사용해 풀어와서 파이썬의 라이브러리를 사용해 순열과 조합을 해결했지만 JavaScript로 언어를 변경하고 순열과 조합에 관련된 라이브러리가 없어 직접 구현을 해야했다. 그래서 이번에는 순열과 조합 구현을 정리해보고자 한다.
조합
서로 다른 n개 중에서 r개를 골라 순서를 상관하지 않고 나열한 경우의 수.(nCr)
예를 들어 [1, 2, 3, 4]중 3개를 골라 순서를 상관하지 않고 나열한다면(4C3) 결과는 아래와 같다.
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]위의 결과값은 아래와 같은 과정을 통해 구할 수 있다.
- 1을 선택하고 나머지 [2, 3, 4]중 2개를 골라 순서 상관 없이 나열한다(3C2)
- [1, 2, 3], [1, 2, 4], [1, 3, 4]
- 2를 선택하고 나머지 [3, 4]중 2개를 골라 순서 상관 없이 나열한다(2C2)
- [2, 3, 4]
즉 배열의 처음부터 하나씩 선택하고.나머지 배열에 대해서 조합을 구해서 합치면 되는 것이다. => 재귀 함수를 사용하면 된다!
조합 구현 코드
const getCombinations = (arr, num) => {
const results = [];
// 1개를 고를(nC1) 경우 배열의 모든 요소들을 return
if (num === 1) return arr.map(v => [v]);
//fixed = 배열의 처음부터 하나씩 선택된 요소, index: 현재 fixed된 요소의 index, origin: forEach()를 호출한 배열
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1); //fixed를 제외한 뒤의 나머지 배열 요소들
// 나머지 배열(rest)을 기준으로 다시 조합을 구한다.
// 기준값(fixed)이 있기 때문에 선택하려는 개수(r)에서 - 1 을 해준다.
const combinations = getCombinations(rest, num - 1);
// 기준값(fixed)에 돌아온 조합(combinations)을 붙인다.
const attached = combinations.map(v => [fixed, ...v]);
// 붙인 값을 결과 값에 넣어준다.
results.push(...attached);
});
return results;
}
console.log(getCombinations([1, 2, 3, 4], 3)); //[ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]순열
서로 다른 n개 중 r개를 골라 순서를 고려해 나열한 경우의 수.(nPr = nCr × r!)
조합의 예를 들었던 [1, 2, 3, 4]중 3개를 골라 순서를 고려해 나열한다면(4P3) 조합에서 나온 결과값 [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]에서 순서를 바꾸는 경우를 생각해 구하는 것이고 [1, 2, 3]이 순서를 바꿔서 나열하는 경우는 3 × 2 × 1과 같기 때문에 nCr × n!이 되는 것이다. 결과는 아래와 같다.
[ 1, 2, 3 ], [ 1, 3, 2 ],
[ 1, 2, 4 ], [ 1, 4, 2 ],
[ 1, 3, 4 ], [ 1, 4, 3 ],
[ 2, 1, 3 ], [ 2, 3, 1 ],
[ 2, 1, 4 ], [ 2, 4, 1 ],
[ 2, 3, 4 ], [ 2, 4, 3 ],
[ 3, 1, 2 ], [ 3, 2, 1 ],
[ 3, 1, 4 ], [ 3, 4, 1 ],
[ 3, 2, 4 ], [ 3, 4, 2 ],
[ 4, 1, 2 ], [ 4, 2, 1 ],
[ 4, 1, 3 ], [ 4, 3, 1 ],
[ 4, 2, 3 ], [ 4, 3, 2 ] 따라서 순열 구현 코드는 조합 구현 코드와 똑같고 rest를 구하는 부분만 fixed된 요소 뒤의 나머지 배열에서 fixed된 요소를 뺀 모든 배열 요소로 변경하면 된다.
순열 구현 코드
const getPermutations = (arr, num) => {
const results = [];
// nP1이면 바로 반환한다.
if (num === 1) return arr.map(v => [v]);
arr.forEach((fixed, index, origin) => {
// 순열에서는 조합과 달리 순서만 바뀌면 중복이 아니기때문에 기준값을 제외한 나머지 배열을 넣어준다.
const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
// 나머지 배열을 기준으로 다시 순열을 구한다.
// 기준값(fixed)이 있기 때문에 선택하려는 개수에서 - 1 을 해준다.
const permutations = getPermutations(rest, num - 1);
// 기준값(fixed)에 순열(permutations)을 붙인다.
const attached = permutations.map(v => [fixed, ...v]);
// 붙인 값을 결과 값에 넣어준다.
results.push(...attached);
});
return results;
}
console.log(getPermutations([1, 2, 3, 4], 3));
// [ 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 ]참고
