조합

서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 택할 때, 이것을 n개에서 r개를 택하는 조합이라 하고, 이 조합의 수를 기호로 nCr과 같이 나타낸다.

예를 들어, 4C3이 인풋으로 주어진다면 다음과 같이 아웃풋이 리턴되어야 한다.

Input: [1, 2, 3, 4];
Output: [
  [1, 2, 3],
  [1, 2, 4],
  [1, 3, 4],
  [2, 3, 4],
];

이때 조합은 순서를 상관하지 않는다. 즉 [1,2,3] = [3,2,1] 이렇게 순서가 바뀌어도 같은 구성인 하나의 조합으로 취급한다.

Sudo Code

그렇다면 코드로 구현한다면 어떻게 해야할까? 순서는 다음과 같다.

배열에서 첫 번째 요소를 선택(고정)한다.
1. 나머지 요소들로부터 조합을 구한다.
2. 선택된 요소와 나머지 조합을 결합한다.
두 번째 요소를 선택(고정)하고, 나머지 요소들로부터 조합을 구한다.
이런 식으로 배열의 마지막 요소까지 반복한다.
더 이상 고정할 요소가 없거나 남은 요소의 개수가 구하려는 조합보다 적을 경우, 조합을 반환한다.
이 과정을 재귀적으로 처리하여 모든 조합을 구한다.

예시:

1을 선택 → 나머지 [2,3,4] 중에서 2개씩 조합
1. [2,3], [2,4], [3,4] 가 반환된다.
2. 여기에 고정된 1을 각각 결합하여 [1,2,3], [1,2,4], [1,3,4] 가 최종 결과로 반환된다.
2를 선택 → 나머지 [3,4] 중에서 2개씩 조합
1. [3,4] 가 반환된다.
2. 여기에 고정된 2를 결합하여 [2,3,4] 가 최종 결과로 반환된다.
3을 선택 → 나머지 [4] 중에서 2개씩 조합
1. 나머지 [4]에서 2개씩 조합을 구하려고 하지만, 남은 요소의 개수가 부족하므로 빈 배열을 반환한다.
4를 선택 → 나머지 요소 없음
1. 나머지 요소가 없으므로 빈 배열을 반환한다.

위 수도코드를 기반으로 조합 알고리즘을 구현해보면 다음과 같다.

function combinations(arr, n) {
  // 만약 조합의 길이가 1이면 배열의 각 요소를 배열로 감싸서 반환
  // 예: [1, 2, 3]에서 1개씩 뽑는 경우 -> [[1], [2], [3]]
  if (n === 1) return arr.map((v) => [v]);
 
  const result = []; // 최종 결과를 저장할 배열
 
  // 배열의 각 요소를 고정(fixed)하고, 고정된 요소 뒤의 나머지 요소들로 재귀적으로 조합을 구함
  arr.forEach((fixed, idx, arr) => {
    // 현재 고정된 요소 이후의 배열(rest)을 구함
    const rest = arr.slice(idx + 1);
 
    // 나머지 배열(rest)에서 n-1개의 조합을 재귀적으로 구함
    const combis = combinations(rest, n - 1);
 
    // 고정된 요소(fixed)를 앞에 붙여 최종 조합을 만듦
    const combine = combis.map((v) => [fixed, ...v]);
 
    // 최종 조합을 결과 배열(result)에 추가
    result.push(...combine);
  });
 
  // 모든 조합을 반환
  return result;
}

순열

순열은 조합과 달리 순서가 중요한 경우의 수를 구하는 문제이다. 조합은 고정된 요소 뒤의 나머지 요소들로만 조합을 구하는 반면, 순열은 모든 요소를 대상으로 고정된 요소를 제외한 나머지 요소들로 순서를 고려하여 조합을 구해야 한다.

위에서 조합을 구할 때 사용했던 알고리즘과 거의 유사하지만, 나머지 요소를 구하는 부분에서 차이가 발생한다.

조합은 고정된 요소 이후의 배열을 구했다면, 순열은 현재 요소를 제외한 나머지 배열을 구하도록 처리해야 한다.

따라서 순열은 구하는 알고리즘의 코드는 다음과 같다.

function permutations(arr, n) {
  // 조합처럼 n이 1이면, 배열의 각 요소를 배열로 감싸서 반환
  if (n === 1) return arr.map((v) => [v]);
 
  const result = []; // 결과를 저장할 배열
 
  // 배열의 각 요소를 고정(fixed)하고, 나머지 요소들로 재귀적으로 순열을 구함
  arr.forEach((fixed, idx, arr) => {
    // 현재 요소를 제외한 나머지 배열(rest)
    const rest = arr.filter((_, index) => index !== idx);
 
    // 나머지 요소들로 순열을 구함
    const permus = permutations(rest, n - 1);
 
    // 고정된 요소(fixed)를 앞에 붙여 순열을 만듦
    const combine = permus.map((v) => [fixed, ...v]);
 
    // 결과 배열에 추가
    result.push(...combine);
  });
 
  // 모든 순열을 반환
  return result;
}

JS 순열 / 조합 알고리즘

Algorithm

조합

Sudo Code

순열