고등학생 때 공부했던 ‘조합’과 ‘순열’…
이를 컴퓨터 알고리즘으로 어떻게 표현할 수 있을까?
우선 ‘조합’에 대해서 이야기해보자.

조합

  • Combination
  • 표현: nCr
  • 의미: 서로 다른 n개 중에서 r개를 뽑을 때, 순서와 상관없이 뽑는 경우의 수.
    중복을 포함하지 않는다. (중복을 포함하는 것은 ‘중복 조합’)

조합의 점화식

조합을 알고리즘으로 표현하기 위해서는 다음과 같은 점화식을 알아야 한다.

nCr = n-1Cr-1 + n-1Cr

예를 들어 원소 0, 1, 2에서 2개를 뽑을 경우, (0, 1), (0, 2), (1, 2)의 3가지 경우가 있다.
이는 다음과 같은 두 가지 케이스로 나눌 수 있다.

0을 뽑은 경우
0을 뽑지 않은 경우

첫 번째 경우는 0이 확정되었으므로, 나머지 2개의 원소 중 남은 1개를 뽑아야 한다. n-1Cr-1

두 번째 경우는 0을 뽑지 않았으므로, 나머지 2개의 원소 중 2개를 뽑아야 한다. n-1Cr

조합을 구하는 식은 언제나 이렇게 나누어진다.
이러한 사실을 활용하면 조합을 간단하게 구현할 수 있다.

function combination(n, r) {
  if (n === r || r === 0) return 1;
  return combination(n - 1, r - 1) + combination(n - 1, r);
}

console.log(combination(5, 3)); // 10
console.log(combination(3, 2)); // 3
console.log(combination(3, 1)); // 3

매우 간단하다!
조합의 점화식은 재귀적으로 구현하고,
n과 r이 같거나 r이 0인 경우만 1로 처리하면 된다.
(재귀의 위대함을 다시 한 번 깨닫는다…)

조합의 경우

자 이제 실제 조합의 경우를 구해보도록 하자.
배열 [0, 1, 2, 3]에서 3개를 뽑는 조합을 구해보겠다. 4C3
이는 다음과 같이 나타낼 수 있다.

  • 0을 선택한 뒤, 나머지 [1, 2, 3]에서 2개의 조합을 구한다.
    => [0, 1, 2], [0, 1, 3], [0, 2, 3]
  • 1을 선택한 뒤, 나머지 [2, 3]에서 2개의 조합을 구한다.
    => [1, 2, 3]
  • 2를 선택한 뒤, 나머지 [4]에서 2개의 조합을 구한다.
    => 없음
  • 3을 선택한 뒤, 나머지 []에서 2개의 조합을 구한다.
    => 없음

재귀의 패턴이 보인다는 것을 알 수 있다.
이를 자바스크립트로 구현해보면 다음과 같다.

// 배열 arr의 요소 중에서 r개를 뽑은 결과를 배열로 반환
function getCombinationElem(arr = [], r) {
  const result = [];
  // 1개를 뽑는 경우, 배열의 모든 요소를 반환한다
  if (r === 1) return arr.map(elem => [elem]);

  // 배열의 요소를 차례대로 선택(fixed)한다
  arr.forEach((fixed, index, array) => {
    // 선택한 요소를 제외한 나머지 배열
    const rest = array.slice(index + 1);

    // 나머지에 대하여 조합을 재귀적으로 계산한다
    const combination = getCombinationElem(rest, r - 1);

    // 계산된 결과를 result 배열에 삽입한다
    combination.forEach(elem => result.push([fixed, ...elem]));
  });
  return result;
}

console.log(getCombinationElem([0, 1, 2, 3], 3));
// [ [ 0, 1, 2 ], [ 0, 1, 3 ], [ 0, 2, 3 ], [ 1, 2, 3 ] ]

이상으로 조합 알고리즘에 대해서 정리해보았다.
조합은 데이터를 처리할 때 유용하므로,
함수를 잘 숙지해두면 매우 큰 도움이 된다!

참고자료

  • https://gorakgarak.tistory.com
  • https://pul8219.github.io