자바스크립트 - 순열과 조합

순열과 조합은 기능을 만들거나, 코딩테스트에서 자주 사용한다. 하지만 자바스크립트는 파이선과 같은 언어와 달리 자체적으로 제공해주는 함수가 없기 때문에 직접 구현해야한다. 

 

순열과 조합은 재귀함수로 만들 수 있는데, n이 무수히 크지 않는다면( 성능을 많이 요구하지 않고, 빠르게 구현한다면 ) 재귀를 사용하여 구현하는 것이 편하다. 

 

순열  

순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 있음)

function permutations(arr, n) {
  // 1개만 뽑는다면 그대로 순열을 반환한다. 탈출 조건으로도 사용된다.
  if (n === 1) return arr.map((v) => [v]);
  let result = [];

  // 요소를 순환한다
  arr.forEach((fixed, idx, arr) => {
    // 현재 index를 제외한 요소를 추출한다.
    // index번째는 선택된 요소
    const rest = arr.filter((_, index) => index !== idx);
    // 선택된 요소를 제외하고 재귀 호출한다.
    const perms = permutations(rest, n - 1);
    // 선택된 요소와 재귀 호출을 통해 구한 순열을 합쳐준다.
    const combine = perms.map((v) => [fixed, ...v]);
    // 결과 값을 추가한다.
    result.push(...combine);
  });

  // 결과 반환
  return result;
}

 

조합

조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 없음)

function combinations(arr, n) {
  // 1개만 뽑는다면 그대로 조합을 반환한다. 탈출 조건으로도 사용된다.
  if (n === 1) return arr.map((v) => [v]);
  const result = [];

  // 요소를 순환한다
  arr.forEach((fixed, idx, arr) => {
    // 현재 index 이후 요소를 추출한다.
    // index번째는 선택된 요소
    const rest = arr.slice(idx + 1);
    // 선택된 요소 이전 요소들을 제외하고 재귀 호출한다.
    const combis = combinations(rest, n - 1);
    // 선택된 요소와 재귀 호출을 통해 구한 조합을 합쳐준다.
    const combine = combis.map((v) => [fixed, ...v]);
    // 결과 값을 추가한다.
    result.push(...combine);
  });

  // 결과 반화
  return result;
}