1. 조합

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

예시를 봐보자

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

4개 중에 3개를 고를 때, 나올수 있는 조합의 경우의 수는 4가지 이다.
여기서 [ 1,2,3 ] = [ 2,1,3 ]인데 이는 조합에서 순서는 상관이 없다는 것을 의미한다

수도코드

시작
  1을 선택(고정)하고 -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구한다.
  [1, 2, 3] [1, 2, 4] [1, 3, 4]
  2를 선택(고정)하고 -> 나머지 [3, 4] 중에서 2개씩 조합을 구한다.
  [2, 3, 4]
  3을 선택(고정)하고 -> 나머지 [4] 중에서 2개씩 조합을 구한다. 
  [] 
  4을 선택(고정)하고 -> 나머지 [] 중에서 2개씩 조합을 구한다.
  []
종료

배열의 처음 원소를 먼저 고정시키고, 나머지 배열에 대한 조합을 구하는 방식이다
나머지에 대한 작업을 수행할 때는 조합을 구하는 코드에 대해서는 한번만 작성하고, 들어가는 인자를 바꾸어주기만 하면 되는 재귀 함수를 사용하면 좋다.

실제 코드

// 배열과 조합의 수를 인자로 전달받으며
function getCombinations(arr, selectNumber){
    let results = [];
  
// 만약, 조합의 수가 1이라면 재귀함수를 종료하게 되어있다
     if (selectNumber === 1) 
         return arr.map((value) => [value]);
    
  // 배열 각각에 대한 원소를 순회한다
    arr.forEach((elem , index, origin)=>{
      // 시작 인덱스보다 하나 더 앞에서 나머지 배열을 가져온다
        const rest = origin.slice(index + 1); 
      // 그 나머지 배열과 조합의수 -1의 값을 다시 재귀함수로 호출
        const combinations = getCombinations(rest, selectNumber - 1); 
        const attached = combinations.map((combination) => [elem, ...combination]); 
        results.push(...attached);
    })
    results = results.map(result =>{
        result.sort();
        return result.join('');
    })
    return results;
}

2. 순열

서로 다른 n개의 물건 중에서 r개를 택하여 한 줄로 배열하는 것을 n개의 물건에서 r개 택하는 순열이라 하고, 이 순열의 수를 기호로 nPr로 나타낸다.

조합은 순서에 상관없이 선택한 것이라면, 순열은 순서가 중요하다.
실제로 순열을 구하는 공식도 조합으로부터 도출 가능하다.

예시를 살펴보자

Input: [1, 2, 3, 4] 
Output: [
          [ 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 ] 
  		]

4개 중에 3개를 선택하고, 순서가 있으므로 4 * 3 * 2 * 1 = 24가지의 순열이 도출된다

수도코드

재귀의 종료 조건은 조합과 동일하다
1,2,3,4를 각각 순서대로 가져오면서 나머지 요소만으로 이루어진 배열에서 selectNumber -1 만큼을 선택하여 재귀를 실행하면 된다

1(fixed) => permutation([2, 3, 4]) => 2(fixed) => permutation([3, 4]) => ...
2(fixed) => permutation([1, 3, 4]) => 1(fixed) => permutation([3, 4]) => ...
3(fixed) => permutation([1, 2, 4]) ... 위와 동일...
4(fixed) => permutation([1, 2, 3])

실제 코드

 const getPermutations = function (arr, selectNumber) {
    const results = [];
    if (selectNumber === 1) return arr.map((el) => [el]); 
    // n개중에서 1개 선택할 때(nP1), 바로 모든 배열의 원소 return. 1개선택이므로 순서가 의미없음.

    arr.forEach((fixed, index, origin) => {
      const rest = [...origin.slice(0, index), ...origin.slice(index+1)] 
      // 해당하는 fixed를 제외한 나머지 배열 
      const permutations = getPermutations(rest, selectNumber - 1); 
      // 나머지에 대해서 순열을 구한다.
      const attached = permutations.map((el) => [fixed, ...el]); 
      //  돌아온 순열에 떼 놓은(fixed) 값 붙이기
      results.push(...attached); 
      // 배열 spread syntax 로 모두다 push
    });

    return results; // 결과 담긴 results return
}