[JS] 자바스크립트로 순열과 조합 구현 정리

1. 순열 ( nPr )

:서로 다른 n개중에 r개를 선택하는 경우의 수 (순서 상관 있음)
ex) 콘서트 곡 순서 👉 a곡, b곡, c곡 != a곡, c곡, b곡

📝 이해해보기

먼저 코딩이 아닌 수학문제라고 가정하고 순열을 어떻게 풀었는지 생각해보자

그럼 이런식으로 하나를 고정하고 경우의 수를 고려하는 방식으로 풀었을 것이다 즉 앞자리가 1일 때 3!, 2일 때 3!, 3일 때 3!, 4일 때 3! = 4! / 1!

그럼 다시 돌아와서 어떻게 코드를 짤지 생각해보면

Input: [1, 2, 3, 4] 

[1, 2, 3]  => 3! 
[1, 2, 4]  => 3!
[1, 3. 4]  => 3!
[2, 3, 4]  => 3!

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

즉, 조합에서 나온 배열마다 순서가 바뀌는 경우의 수를 생각해줘야 한다.

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]) => 1(fixed) => permutation([2, 4]) => ...
4(fixed) => permutation([1, 2, 3]) => 1(fixed) => permutation([2, 3]) => ...

🖋 구현

 const getPermutations = function (arr, selectNumber) {
    const results = [];
   // nP1일 경우
    if (selectNumber === 1) return arr.map((el) => [el]); 
   
   // arr = [1,2,3,4] selectNumber = 3
   // forEach((item, index, arr) => 
    arr.forEach((fixed, index, origin) => {
      // fixed를 제외한 나머지 배열
      const rest = [...origin.slice(0, index), ...origin.slice(index+1)] 
      // 나머지 배열에 대한 순열
      const permutations = getPermutations(rest, selectNumber - 1); 
      
      // rest에 떼 놓은 fixed 값을 붙여줌
      const attached = permutations.map((el) => [fixed, ...el]); 
      // attached를 spread syntax로 복사해 push
      results.push(...attached); 
    });

    return results; 
}

---

2. 조합 ( nCr )

:서로 다른 n개중에 r개를 선택하는 경우의 수 (순서 상관 없음)
ex) 콘서트에 참가할 가수의 조합 (oasis, radiohead) = (radiohead, oasis)

📝 이해해보기

조합의 경우 더 간단하다

그냥 순열에서 중복을 없애주면 된다 4! / 1!3!

예를들어 4C3의 경우

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

시작
  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개씩 조합을 구한다.
  []
종료

🖋 구현

 const getCombinations = function (arr, selectNumber) {
    const results = [];
   // nC1일 경우
    if (selectNumber === 1) return arr.map((el) => [el]); 
   
   // arr = [1,2,3,4] selectNumber = 3
   // forEach((item, index, arr) => 
    arr.forEach((fixed, index, origin) => {
      // fixed를 제외한 나머지 배열
      const rest = origin.slice(index + 1); 
      // 나머지 배열의 조합
      const combinations = getCombinations(rest, selectNumber - 1); 
   
      // rest에 떼 놓은 fixed 값을 붙여줌
      const attached = combinations.map((el) => [fixed, ...el]); 
      // attached를 spread syntax로 복사해 push
      results.push(...attached); 

    });

    return results; 
}