들어가며

순열과 조합에 대해서 배우면서 반복문을 통한 구현부터 재귀를 통한 구현까지 익혔다. 그 중 활용도가 가장 높고 가장 난해한 재귀에 대해서 정리하는 글을 남긴다. 처음 이 코드와 설명을 봤을 때 이해하기가 굉장히 어려웠다. 다른 사람들에게 설명할 때 턱턱 막히는 부분이 있었고 그 부분을 중점적으로 정리하려고 한다.

코드를 처음보고 3일정도 개념을 생각하거나 카피 타이핑을 하곤 했고 일상생활 중 간간히 생각했다. 어려운 개념은 반복적인 노출과 암기를 통한 이해. 그리고 멘탈 관리다.

내가 참고한 설명과 코드는 아래 블로그에서 참고했다.
JavaScript로 순열과 조합 알고리즘 구현하기 by 춤추는개발자

순열과 조합이란?

순열과 조합은 주어진 숫자 중 주어진 모음에서 만들 수 있는 경우의 수를 의미한다. 이는 모든 조건을 확인해야하는 완전탐색 과정임을 예상할 수 있다.

조합

• 조합은 중복을 허용하지 않고 순서가 중요하지 않다.

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

• selectNum === 1 일 때 남은 모든 요소에 배열을 씌워서 리턴한다.
  왜냐면 다른 실행 결과들도 배열로 리턴되기 때문이다.
• 배열 forEach 문으로 완전 탐색을 구현한다. 모든 경우의 수와 인덱스를 돌아본다.
• 조합은 숫자 하나를 고정해놓고 나머지 수 중에서 조합을 찾는다.
  • rest 변수는 fixed 값의 인덱스를 제외한 나머지 배열을 가진다. origin.slice(index + 1)로 구현되었기 때문에 인덱스 이후 배열만을 저장할 수 있다.
    • 마지막 숫자에 가까워질수록 index가 진행되기 때문에 만들 수 있는 rest, 조합의 수는 점점 줄어든다.
  • 조건이 바뀌고 getCombinations(rest, selectNum - 1) 동일한 동작이 반복된다.
  • 재귀가 실행된 결과(combinations)는 attached 변수에 fixed 값과 합쳐진 후 배열의 요소로 저장된다.
  • 결과를 spread 문법으로 result에 저장한 후 반복문을 마저 실행한다.
• result에는 수 하나를 제외한 나머지 숫자들이 합쳐진 배열을 가지고 있다.
• 만약 주어진 배열보다 조합의 수가 더 크다면 빈배열이 반환된다.

function getCombinations (arr, selectNum) {
  if (selectNum === 1) return arr.map(el => [el])
  
  const result = [];
  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    const combinations = getCombinations(rest, selectNum - 1);
    const attached = combinations.map(el => [fixed, ...el]);
    result.push(...attached);
  })
  return result;
}

const example = [1,2,3,4];
const result = getCombinations(example, 3);
console.log(result);

순열

• 순열은 중복을 허용하고 순서가 중요하다.

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

• 순열은 조합에서 코드 딱 한 줄만 바뀌었다. 고정할 숫자를 제외한 rest 변수에 할당하는 부분이다.
• 순열은 중복이 가능하고 순서가 중요하다. 따라서 인덱스를 진행시키면서 조합의 가능성을 줄일 필요가 없다.
• 조합은 자신과 이전 숫자를 제외시키면서 인덱스를 진행한다.
  rest = origin.slice(index + 1);
  순열은 자신을 고정 및 제외. 이전 숫자, 이후 숫자 모두 포함한다.
  rest = [...origin.slice(0, index), ...origin.slice(index + 1)]
• 자신을 제외하고 남은 숫자끼리 가능한 조합을 찾는다. 그 안에서 다시 자신을 제외하고 남은 숫자끼리 조합을 찾는다. 따라서 요소의 수가 일정하다.

function getCombinations (arr, selectNum) {
  if (selectNum === 1) return arr.map(el => [el])
  
  const result = [];
  arr.forEach((fixed, index, origin) => {
    //const rest = origin.slice(index + 1); 조합의 경우
    const rest = [...origin.slice(0, index),  ...origin.slice(index + 1)]
    const combinations = getCombinations(rest, selectNum - 1);
    const attached = combinations.map(el => [fixed, ...el]);
    result.push(...attached);
  })
  return result;
}

const example = [1,2,3,4];
const result = getCombinations(example, 3);
console.log(result);