[TIL] 순열과 조합

순열 (Permutation)

순열은 n개 중에 r개를 뽑는 경우의 수를 구할 때 순서를 고려하여 뽑는 개념이다.
순서를 고려한다는 말은 배열 [1, 2, 3]과 배열 [2, 1, 3]을 다른 것으로 본다는 말이다.

배열 [1, 2, 3, 4] 를 중에 3개를 순열로 뽑는 경우 (4P3), 다음과 같은 결과값이 나온다.

[[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]]

그 값을 구하는 방법을 쫓아가보자.

n = 4, r = 3
1. 먼저 1을 선택하고 r을 1 뺀다.
2. 나머지 [2, 3, 4] 중에서 순열을 구한다. (n = 3, r = 2)
3. 위의 순서로 [3, 4]의 배열, [4]의 배열에서의 순열까지 구한다.
4. 앞서 선택해둔 값에 차례로 합친다.
5. 순서를 고려하기 때문에 1~4의 과정을 똑같이 2, 3, 4를 먼저 선택하는 방법으로 진행한다.

코드

const getPermutations = (array, num) => {
  const results = [];
  if (num === 1) {
    return array.map((value) => [value]); // 탈출 조건
  }
  
  array.forEach((fixed, idx, origin) => {
    const rest = [...origin.slice(0, idx), ...origin.slice(idx + 1)]; // 해당하는 fixed를 제외한 나머지 배열
    const permutations = getPermutations(rest, num - 1); // 나머지에 대한 순열을 구함
    const attached = permutations.map((permutation) => [fixed, ...permutation]); // 순열에 대해 떼 놓은 fixed 값 붙이기
    results.push(...attached); // 결과 배열에 쌓기
  });
  return results;
}

조합 (Combination)

조합은 n개 중에 r개를 뽑는 경우의 수를 구할 때 순서를 고려하지 않고 뽑는 개념이다.
마찬가지로 순서를 고려하지 않는다는 것은 배열 [1, 2, 3]과 배열 [2, 1, 3]을 같은 것으로 취급한다.

순열에서와 같은 예시로 조합을 구하면, 다음과 같은 결과값이 나온다.

[[1,2,3], [1,2,4], [1,3,4], [2,3,4]]

조합을 구하는 순서

n = 4, r = 3
1. 먼저 1을 선택하고 r을 1 뺀다.
2. 나머지 [2, 3, 4] 중에서 조합을 구한다. (n = 3, r = 2)
3. 그 각각을 선택해둔 선택해둔 값에 붙인다.
4. 순서를 고려하지 않기 때문에 1을 제외한 배열에서부터 1~3 과정을 빈 배열이 될 때까지 반복한다.

코드

조합의 코드는 나머지 배열을 구하는 코드만 변경하면 된다.

const getCombinations = (array, num) => {
  const results = [];
  if (num === 1) {
    return array.map((value) => [value]); // 탈출 조건
  }
  
  array.forEach((fixed, idx, origin) => {
    const rest = origin.slice(idx + 1); // 해당하는 fixed를 제외한 나머지
    const combinations = getCombinations(rest, num - 1); // 나머지에 대한 순열을 구함
    const attached = combinations.map((combination) => [fixed, ...combination]); // 순열에 대해 떼 놓은 fixed 값 붙이기
    results.push(...attached); // 결과 배열에 쌓기
  });
  return results;
}