재귀를 이용한 순열, 조합 구현하기

왜 하는가?

알고리즘 문제를 풀다가, 어떤 숫자 배열에 있는 원소를 조합하여 만들 수 있는 수 중 가장 큰 숫자 라던가 하는 순열, 조합 개념이 들어간 문제를 만났다. 구현하고 탐구해보기로 했다.

풀이 단계

1. reduce 와 재귀호출을 사용해서 각 배열의 원소마다 순회하고 결과를 합친다.
2. 이미 순회한 것을 basket 에 넣는다 (들른 장소를 표시)
3. 순회조건을 설정한다
4. 종료조건

순회조건 설정

공통 배열 설정

function initializeNumbers(n) {
  return Array(n).fill().map((_, idx) => idx + 1);
}

순열

What 원소가 중복되지 않도록 한다
How filter 에서 이미 순회한 원소를 다시 순회하지 않도록 함수를 준다.

function permutation(
  n, r, basket = [], arr = initializeNumbers(n),
) {
  if (basket.length === r) {
    return 1;
  }

  return arr
    .filter((el) => !basket.includes(el)) // 순회 조건 설정
    .reduce((acc, curr) => acc + permutation(n, r, basket.concat(curr), arr), 0);
}

test('permutation', () => {
  expect(permutation(5, 3)).toBe(60);
  expect(permutation(10, 3)).toBe(720);
});

조합

What 순회 순서를 무시한다
How filter 에서 순회 방향을 한가지로 정한다. 이전 원소가 다음 원소 보다 크다, 혹은 작다.

function combination(
  n, r, basket = [], arr = initializeNumbers(n),
) {
  if (basket.length === r) {
    return 1;
  }

  return arr
    .filter((el) => el > Math.max(...basket)) // 순회 조건 설정
    .reduce((acc, curr) => acc + combination(n, r, basket.concat(curr), arr), 0);
}

test('combination', () => {
  expect(combination(5, 3)).toBe(10);
  expect(combination(10, 3)).toBe(120);
});