73일차 - 순열, 조합

알고리즘 테스트 준비 중 순열과 조합 파트를 공부했다.

순열과 조합은 처음 재귀적인 생각을 하는 것이 힘들지 한 번 적응하고 나면 조금씩 바꿔서 응용해 나가면 된다.

가장 기본적인 문제 순열로 간단한 문제를 만들어 보자면

문제 : 중복이 없는 임의의 알파벳으로 이루진 배열을 num개를 뽑을때, 가능한 조합을 배열로 나타내는 함수를 만들어라.

라는 문제가 있다고 해보자.

이 문제는 for문을 n번 돌리면서, 뽑을때 마다 알파벳을 배열에서 제거하면 된다.
그런데 문제는 for문을 몇 번 돌려야할지도 모르고 만약 10개의 알파벳을 뽑는다고 가정하면 for문을 10개 중첩시켜야 한다.
해결법은 재귀로 중첩을 시키는 것이다.

function pickAlphabet (alphabetArr, num) {
  
  let result = [];
  
  function permutate (arr, bucket, n) {
    if (n === 0) {
      result.push(bucket);
      return;
    }
    
    for (let i = 0; i < arr.length; i++) {
      let current = arr[i];
      let sliceArr = arr.slice();
      sliceArr.splice(i, 1);
      permutate (sliceArr, bucket.concat(current), n - 1);
    }
  }
  
  permutate (alphabetArr, [], num);
  
  return result;
}

이렇게 구현하면 만약 pickAlphabet(['a', 'b', 'c'], 3)을 대입하면

["a", "b", "c"]
["a", "c", "b"]
["b", "a", "c"]
["b", "c", "a"]
["c", "a", "b"]
["c", "b", "a"]

이렇게 순열을 구현할 수 있다.