1. 조합(Combinations)
조합은 서로 다른 n개의 원소 중에서 순서를 고려하지 않고 r개를 선택하는 경우의 수를 의미한다.
4C3 = 4Combinations3 은 4개의 원소들 중에서 순서를 고려하지 않고 3개를 선택하여 조합으로 나올 수 있는 경우의 수를 구한다는 의미이다.
Input: [1, 2, 3, 4]
Output: [ [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4] ]예를 들어 주어진 4개의 원소 [1, 2, 3, 4] 중 3개를 선택하여 조합으로 나올 수 있는 경우의 수는 [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]] 와 같다. 조합은 순서를 고려하지 않기 때문에 [1, 2, 3] = [3, 2, 1] 과 같이 순서가 달라도 같은 경우의 수로 취급한다.
자바스크립트 구현
앞선 예시를 자바스크립트로 구현해보자.
시작
1을 선택(고정)하고 -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구한다.
[1, 2, 3] [1, 2, 4] [1, 3, 4]
2를 선택(고정)하고 -> 나머지 [3, 4] 중에서 2개씩 조합을 구한다.
[2, 3, 4]
3을 선택(고정)하고 -> 나머지 [4] 중에서 2개씩 조합을 구한다.
[]
4을 선택(고정)하고 -> 나머지 [] 중에서 2개씩 조합을 구한다.
[]
종료배열의 요소를 처음부터 하나씩 선택(고정)하고 뒤의 나머지 배열에 대한 조합을 구해 고정된 요소에 붙이면 된다. 나머지 배열에 대한 조합을 구할 때는 재귀(Recursion) 함수를 사용한다. 왜냐하면 계속 반복 될 일(나머지 배열에 대한 조합을 구하는 일)에 대해선 들어가는 인자만 바꿔주면 되기 때문이다.
const getCombinations = (arr, selectNumber) => {
const results = [];
// 재귀 종료 조건: 한 개를 선택할 땐, 모든 배열의 요소를 하나씩 선택해 배열로 리턴한다.
if (selectNumber === 1) return arr.map((value) => [value]);
// forEach: 배열의 모든 요소를 처음부터 끝까지 한 번씩 고정(fixed)되게 한다.
arr.forEach((fixed, index, origin) => {
// fixed를 제외하고 뒤의 나머지 배열을 구한다.
const rest = origin.slice(index + 1);
// 나머지 배열에 대한 조합을 구한다.
const combinations = getCombinations(rest, selectNumber - 1);
// 나머지 배열에 대한 조합을 고정(fixed)된 요소에 붙인다.
const attached = combinations.map((combination) => [fixed, ...combination]);
// 최종적으로 만들어진 조합을 전개 연산자를 사용해 results 배열에 담는다.
results.push(...attached);
});
// results를 반환한다.
return results;
};
const arr = [1, 2, 3, 4];
const result = getCombinations(arr, 3);
console.log(result);
// => [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]- 1C2 처럼 배열 원소수보다 선택하려는 개수가 더 많은 경우에는 빈 배열이 리턴되기 때문에 최종 결과값에 포함되지 않는다.
2. 중복 조합
중복 조합은 서로 다른 n개의 원소 중에서 순서를 고려하지 않고, 중복을 허용하여 r개를 선택하는 경우의 수를 의미한다.
const getCombinationsWithRepetition = (arr, selectNumber) => {
const results = [];
// 재귀 종료 조건: 한 개를 선택할 땐, 모든 배열의 요소를 하나씩 선택해 배열로 리턴한다.
if (selectNumber === 1) return arr.map((value) => [value]);
// forEach: 배열의 모든 요소를 처음부터 끝까지 한 번씩 고정(fixed)되게 한다.
arr.forEach((fixed, index, origin) => {
// fixed를 포함하는 뒤의 나머지 배열을 구한다.
const rest = origin.slice(index);
// 나머지 배열에 대한 조합을 구한다.
const combinations = getCombinationsWithRepetition(rest, selectNumber - 1);
// 나머지 배열에 대한 조합을 고정(fixed)된 요소에 붙인다.
const attached = combinations.map((combination) => [fixed, ...combination]);
// 최종적으로 만들어진 조합을 전개 연산자를 사용해 results 배열에 담는다.
results.push(...attached);
});
// results를 반환한다.
return results;
};
const arr = [1, 2, 3, 4];
const result = getCombinationsWithRepetition(arr, 3);
console.log(result);
/* => [
[ 1, 1, 1 ], [ 1, 1, 2 ],
[ 1, 1, 3 ], [ 1, 1, 4 ],
[ 1, 2, 2 ], [ 1, 2, 3 ],
[ 1, 2, 4 ], [ 1, 3, 3 ],
[ 1, 3, 4 ], [ 1, 4, 4 ],
[ 2, 2, 2 ], [ 2, 2, 3 ],
[ 2, 2, 4 ], [ 2, 3, 3 ],
[ 2, 3, 4 ], [ 2, 4, 4 ],
[ 3, 3, 3 ], [ 3, 3, 4 ],
[ 3, 4, 4 ], [ 4, 4, 4 ]
] */- 기존의 조합과 다른 점은
const rest = origin.slice(index);고정된 요소를 제외하는 것이 아니라, 포함한 뒤의 나머지 배열을 구한다는 것이다.
3. 순열(Permutation)
순열은 서로 다른 n개의 원소 중에서 순서를 고려하여 r개를 선택하는 경우의 수를 의미한다.
4P3 = Permutation 은 4개의 원소들 중에서 순서를 고려해 3개를 선택하여 조합으로 나올 수 있는 경우의 수를 구한다는 의미이다.
Input: [1,2,3,4]
Output: [
[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]
]예를 들어 주어진 4개의 원소 [1, 2, 3, 4] 중 3개를 선택하여 순열으로 나올 수 있는 경우의 수는 [[1,2,3],[1,2,4],[1,3,2], ... [4,2,3],[4,3,1],[4,3,2]] 와 같다. 순열은 순서를 고려하기 때문에 [1, 2, 3] != [3, 2, 1] 과 같이 같은 요소를 가지고 있더라도 순서가 다르기 때문에 다른 경우의 수로 취급한다.
자바스크립트 구현
앞선 예시를 자바스크립트로 구현해보자.
1(fixed) -> permutation([2,3,4]) -> 2(fixed) -> permutation(3,4) -> ...
2(fixed) -> permutation([1,3,4]) -> 1(fixed) -> permutation(3,4) -> ...
3(fixed) -> permutation([1,2,4]) -> ...
4(fixed) -> permutation([1,2,3]) -> ...순열은 조합을 구하는 방식과 크게 다르지 않게 구현할 수 있다. 다만, 조합과 다른 점은 배열의 요소를 처음부터 하나씩 선택(고정)하되, 나머지 배열을 구할 때 고정된 요소 뒤에 있는 값이 아니라 고정된 요소를 제외한 모든 요소를 갖도록 하는 것이다. 이후 (고정된 값을 제외한 모든 요소를 갖는) 나머지 배열에 대한 순열을 구해 고정된 요소에 붙이면 된다.
const getPermutations = function (arr, selectNumber) {
const results = [];
// 재귀 종료 조건: 한 개를 선택할 땐, 모든 배열의 요소를 하나씩 선택해 배열로 리턴한다.
if (selectNumber === 1) return arr.map((value) => [value]);
// forEach: 배열의 모든 요소를 처음부터 끝까지 한 번씩 고정(fixed)되게 한다.
arr.forEach((fixed, index, origin) => {
// fixed를 제외한 모든 요소를 갖는 나머지 배열을 구한다.
const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
// 나머지 배열에 대한 순열을 구한다.
const permutations = getPermutations(rest, selectNumber - 1);
// 나머지 배열에 대한 순열을 고정(fixed)된 요소에 붙인다.
const attached = permutations.map((permutation) => [fixed, ...permutation]);
// 최종적으로 만들어진 순열을 전개 연산자를 사용해 results 배열에 담는다.
results.push(...attached);
});
// results를 반환한다.
return results;
};
const arr = [1, 2, 3, 4];
const result = getPermutations(arr, 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 ]
// ]- 조합과 다른 점은
const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];고정된 값을 제외하고 뒤의 나머지 배열을 구하는 것이 아닌, 고정된 값을 제외한 모든 요소를 갖는 나머지 배열을 구한다는 것이다.
4. 중복 순열
중복 순열은 서로 다른 n개의 원소 중에서 순서를 고려하고, 중복을 허용하여 r개를 선택하는 경우의 수를 의미한다.
const getPermutationsWithRepetition = function (arr, selectNumber) {
const results = [];
// 재귀 종료 조건: 한 개를 선택할 땐, 모든 배열의 요소를 하나씩 선택해 배열로 리턴한다.
if (selectNumber === 1) return arr.map((value) => [value]);
// forEach: 배열의 모든 요소를 처음부터 끝까지 한 번씩 고정(fixed)되게 한다.
arr.forEach((fixed) => {
// 원본 배열에 대한 순열을 구한다.
const permutations = getPermutationsWithRepetition(arr, selectNumber - 1);
// 원본 배열에 대한 순열을 고정(fixed)된 요소에 붙인다.
const attached = permutations.map((permutation) => [fixed, ...permutation]);
// 최종적으로 만들어진 순열을 전개 연산자를 사용해 results 배열에 담는다.
results.push(...attached);
});
// results를 반환한다.
return results;
};
const arr4 = [1, 2, 3, 4];
const result4 = getPermutationsWithRepetition(arr4, 3);
console.log(result4);
/* => [
[ 1, 1, 1 ], [ 1, 1, 2 ], [ 1, 1, 3 ], [ 1, 1, 4 ],
[ 1, 2, 1 ], [ 1, 2, 2 ], [ 1, 2, 3 ], [ 1, 2, 4 ],
[ 1, 3, 1 ], [ 1, 3, 2 ], [ 1, 3, 3 ], [ 1, 3, 4 ],
[ 1, 4, 1 ], [ 1, 4, 2 ], [ 1, 4, 3 ], [ 1, 4, 4 ],
[ 2, 1, 1 ], [ 2, 1, 2 ], [ 2, 1, 3 ], [ 2, 1, 4 ],
[ 2, 2, 1 ], [ 2, 2, 2 ], [ 2, 2, 3 ], [ 2, 2, 4 ],
[ 2, 3, 1 ], [ 2, 3, 2 ], [ 2, 3, 3 ], [ 2, 3, 4 ],
[ 2, 4, 1 ], [ 2, 4, 2 ], [ 2, 4, 3 ], [ 2, 4, 4 ],
[ 3, 1, 1 ], [ 3, 1, 2 ], [ 3, 1, 3 ], [ 3, 1, 4 ],
[ 3, 2, 1 ], [ 3, 2, 2 ], [ 3, 2, 3 ], [ 3, 2, 4 ],
[ 3, 3, 1 ], [ 3, 3, 2 ], [ 3, 3, 3 ], [ 3, 3, 4 ],
[ 3, 4, 1 ], [ 3, 4, 2 ], [ 3, 4, 3 ], [ 3, 4, 4 ],
[ 4, 1, 1 ], [ 4, 1, 2 ], [ 4, 1, 3 ], [ 4, 1, 4 ],
[ 4, 2, 1 ], [ 4, 2, 2 ], [ 4, 2, 3 ], [ 4, 2, 4 ],
[ 4, 3, 1 ], [ 4, 3, 2 ], [ 4, 3, 3 ], [ 4, 3, 4 ],
[ 4, 4, 1 ], [ 4, 4, 2 ], [ 4, 4, 3 ], [ 4, 4, 4 ]
] */- 기존의 순열과 다른 점은
const permutations = getPermutationsWithRepetition(arr, selectNumber - 1);고정된 값을 제외한 모든 요소를 갖는 나머지 배열을 구할 필요 없이 원본 배열, 즉 모든 요소를 갖는 배열을 가지고 순열을 구한다는 것이다.
참조
