[TIL] 순열과 조합(JS)

코딩테스트를 하며 자주 쓰게 되는 간단한 알고리즘을 공부했다.
외우면 빠르게 적용가능하다고 생각해 TIL에 정리해보기로 했다.
오늘은 재귀를 통해 특정 배열과 원소개수가 주어졌을 때, 순열과 조합을 출력하는 코드를 작성해보았다.

---

순열

순열이란 순서를 정해 나열한 것을 의미한다.

nPr = n (n-1) … * (n-r+1)
nPn = n!
순열 알고리즘을 재귀로 구현했을 때, 시간복잡도는 O(N!)

function getProduct(arr, k) {
  if (k === 0) return [[]];
  const result = [];
  const prev = getProduct(arr, k - 1);
  for (const p of prev) {
    for (const a of arr) {
      result.push([...p, a]);
    }
  }
  return result;
}

[예시]

getProduct([10,20,30], 2) 의 경우

1. prev 에서 getProduct([10,20,30], 1)을 호출
2. getProduct([10,20,30], 0)을 호출
3. getProduct([10,20,30], 0)은 [[]]을 return하고 이 값은 prev가 됨.
4. for문을 도는데, 이때 배열의 요소는 [] 하나이므로, arr의 각 a가 result에 push된다. [[10], [20], [30]] 을 리턴한다.
5. for문을 다시 돈다. prev의 요소가 3개이므로, 3(prev)*3(arr), 9개를 리턴하고 종료한다.

[
  [ 10, 10 ], [ 10, 20 ],
  [ 10, 30 ], [ 20, 10 ],
  [ 20, 20 ], [ 20, 30 ],
  [ 30, 10 ], [ 30, 20 ],
  [ 30, 30 ]
]

조합

조합은 순열과 다르게 순서를 정하지 않고 나열한 것을 의미한다.

nCr = n! / (n-r)! (r)!
시간복잡도는 O(2^n)

function getCombinations(arr, k) {
 if (k === 0) return [[]];
 if (k > arr.length) return [];

 const result = [];

 for (let i = 0; i < arr.length; i++) {
   const head = arr[i];
   const prev = getCombinations(arr.slice(i + 1), k - 1);
   for (const p of prev) {
     result.push([head, ...p]);
   }
 }

 return result;
}

[예시]

getProduct([10,20,30], 2) 의 경우

1. head[i]가 10일 때
   1-1. prev 에서 getCombination([20,30], 1)을 호출
   1-2. 1을 진행하며 getCombination([30], 0)을 호출
   1-3. [[]]으로 for문을 진행한다. 그 뒤 [[20],[30]] 리턴한다.
   1-4. [[20],[30]]으로 for문을 진행한다. 이후 result에 head를 추가한[10,20]와 [20,30]를 추가한다.
2. head[i]가 20일 때
   2-1. prev에서 getCombination([30],1)을 호출한다.
   2-2. [[30]]를 리턴하고 다시 for문 진행
   2-3. head를 추가한 [20,30]을 result에 추가한다.
3. head[i]가 30일 때
   3-1. prev에서 getCombination([],1) 을 호출한다.
   3-2. arr의 길이가 1보다 작으므로 빈배열을 출력함. result에 push되는 것은 없다.

[
  [ 10, 20 ],
  [ 10, 30 ],
  [ 20, 30 ]
]