순열(Permutation)

고등학교 수학시간에 안 졸았다면 확률과 통계에서 배운 기억이 있을 것이다. 그 배운 내용을 토대로 완전 탐색을 구현해보고자 한다.

 알고리즘 문제를 풀다보면 완전탐색으로 풀어야될 문제가 종종 보인다. 예를 들어 arr = [1,2,3,4] 배열의 원소들로 만들수 있는 자리의 숫자를 만들때 완전탐색이란 알고리즘을 사용하면 된다.

순열의 정의

 순열은 서로 다른 경우 n개 중에 r개를 선택하는 경우의 수를 의미 한다.이 순열의 수를 기호로 nPr와 같이 나타낸다. 또한 이 경우의 수를 구하는 순열의 수는 n의 계승이라고 하며 n!로 나타낸다.
이때 순서 즉 위에 예를 바탕으로 설명하자면

arr = [1,2,3,4] 를 이용해 4자리 숫자를 만들 경우를 생각하면 첫번째자리에 올수있는 경우는 4가지이고 두번째자리에 올수 있는 경우가 앞에서 하나 빠졌기 때문에 3가지이다. 이런식으로 해서

4*3*2*1

이 되게 되며 답은 24가지이다.

nPr = $\frac{n!}{(n-r)!r!}$

로 나타낼수 있다.

순열(완전탐색)으로 가능한 모든 조합 찾기

완전탐색 : 전체요소를 일일이 순회하며 가능한 모든 요소를 도출해 경우의 수를 구하는 것

 완전 탐색을 구현 할수 있는 방법에는 브루트 포스, 비트 마스트, 백 트래킹, 순열이 있는 데 우리에게 제일 친숙한 것이 순열이기 때문에 순열이 제일 좋다고 생각한다.

 구현 방식은 다음과 같다.

let arr = [1,2,3]// 예
/*=>1 고정 => 123 => 12 
          => 132 => 13
  =>2 고정 => 213 => 21
          => 231 => 23
  =>3 고정 => 321 => 32
          => 312 => 31
          

한 숫자를 고정하고 요소들을 바꾸는 방식으로 되어야 할것 같았다. 경우의 수가 많아 진다면 다른 숫자들도 고정할 필요가 있다고 생각했다. 그러다가 코드를 작성하며 디버깅 해본 결과 그럴 필요 없다고 확신이 들었다.

function solution(arr) {
  let result = [];
  function getPermutation(arr, fixed) {
    if (arr.length >= 1) {
      for (let i = 0; i < arr.length; i++) {
        const newFixed = fixed + arr[i];
        const copyArr = arr.slice();
        copyArr.splice(i, 1);
        result.push(parseInt(newFixed));
        getPermutation(copyArr, newFixed);
      }
    }
    return arr[0];
  }
  getPermutation(arr, '');
  return result;
}

위에 로직을 보면 루프를 돌면서 배열 순서 대로 돌기 때문에 굳이 두번째 고정값을 둘 필요가 없겠구나 생각했다.

완전 탐색 알고리즘 설명 :

함수가 처음에 빈 고정값을 갖고 배열과 실행이 되면 루프를 한번 돈다. 그리고 빈고정값에 첫번째 요소를 더한다. 그러면 newFixed에 담길 것이다. 그리고 기존 배열 부분을 복사해서 루프가 돌고 있는 부분만 잘라서 그 부분은 결과에 푸쉬 해준다. 나머지를 재귀를 돌려 주면 또다시 고정이 되면서 원하는 결과 도출이 가능 하다.

TMI :

위 코드를 조금만 수정한다면 조합의 경우도 구현할수도 있을거 같았다. 그건 다음에 포스팅해야겠다.

solution([1, 2, 3]) [
    1,  12, 123,  13, 132,  2,
   21, 213,  23, 231,   3, 31,
  312,  32, 321
]