순열

순열이란 n개의 원소를 갖는 집합에서 r개의 원소를 순서를 생각하고 중복 없이 선택하는 것이다.

주로 완전 탐색(brute force) 문제를 풀 때 사용하게 된다. C++로 알고리즘 문제를 풀 때는 next_permutation 함수로 순열과 조합을 구할 수 있었지만, 자바스크립트에는 순열 조합과 관련된 내장 함수가 없다고 하여 직접 구현하는 방식의 코드를 이해한대로 정리해 보았다.

구현 아이디어

순열을 구현하는 아이디어는 첫 번째 위치할 수를 골라 놓고 나머지를 구성하는 것이다. 이때, 중복되는 알고리즘은 재귀로 처리한다.

흐름

5개의 원소가 있는 [1,2,3,4,5] 배열에서 3개를 선택하는 순열을 구하는 경우(5P3)

1. 첫 번째 원소가 1인 경우

   1-1. 1은 고정하고 [2,3,4,5]에서 두 개 선택

   3개를 선택해야 하는데 첫 번째 원소로 1을 선택했으므로 1을 제외한 나머지 원소들 중에서 두 개를 선택하면 된다.

   // func([1,2,3,4,5], 3)
   const fix=1;
   const rest=[2,3,4,5];
   const permutationOfRest=func([2,3,4,5], 2); // 재귀 호출 발생

   이번에는 [2,3,4,5]에서 첫 번째 원소로 2를 선택한 다음 2를 제외한 나머지 원소들 중에서 한 개를 선택하면 된다.

   // func([2,3,4,5], 2)
   const fix=2;
   const rest=[3,4,5]
   const permutationOfRest=func([3,4,5], 1); // 재귀 호출 발생

   마지막으로 [3,4,5]에서 한 개를 선택하면 되는데 [3,4,5]에서 한 개를 선택하는 방법은 정해져 있다. 따라서 1개를 선택하는 경우엔 인수로 받은 배열을 해체해 반환해 주면 된다. 즉, 1개를 선택하는 경우가 재귀 호출의 종료 조건이 된다.

   // func([3,4,5], 1);
   return [[3],[4],[5]];

   이제 func([3,4,5], 1)의 반환값을 알게 되었으니, 바로 윗 단계에서 선택한 원소 2를 각 요소 맨 앞에 넣어주면 func([2,3,4,5], 2)의 반환값을 알 수 있게 된다.

   // func([2,3,4,5], 2)
   return [[2,3], [2,4], [2,5]];

   이제 func([2,3,4,5], 2)의 반환값을 알게 되었으니, 그 윗 단계에서 선택한 원소 1을 각 요소 맨 앞에 넣어주면 최종적으로 첫 번째 원소가 1인 경우의 수 즉, func([1,2,3,4,5], 3)의 값을 구할 수 있게 된다.

   // func([1,2,3,4,5], 3)
   return [[1,2,3], [1,2,4], [1,2,5]];

위의 과정을 총 5회 반복하면 된다.

소스 코드