[JS] 순열(Permutation)

순열이란

순열이란 n개의 원소를 갖는 집합에서  순서를 생각하고 중복 없이 모든 경우의 수를 선택하는 것을 말합니다. 백트래킹(backtracking)/ DFS 를 활용하여 문제를 접근할 수 있습니다. 

ex) 집합이 ["a" , "b", "c"] 주어질 때   

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

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

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

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

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

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

 

순열구현

집합이 ["a" , "b", "c"] 주어질  때  요소 a,b,c를 각각 순서대로 픽스하고 나머지 요소만으로 이루어진 배열에서 (seletNumber-1)만큼을 선택하여 또 순열을 구한다.(재귀)

function getPermutation (array, selectNumber) {

 if (selectNumber === 1) return array. map((element) =› [element]);
 const result = [];
 array. forEach ((element, originalArrIndex, array) = {
 const fix = element;
  const rest = array. filter ((_, restArrIndex) => restArrIndex !== originalArrIndex);
const permutation0fRest = getPermutation (rest, selectNumber - 1) ;
const combineFix = permutation0fRest .map ((elementArr) = [fix, ... elementArr]);
result.push (... combineFix);
});
return result;
}

getPermutation ([1,2,3], 3) ; 했다고 가정할 때

->해석: 집합[1,2,3]에서 3개의 원소를 순서를 생각하고 중복 없이 선택해주세요

 

1. 배열 순회 

첫번째 요소가 1로 고정될 경우, 2일 경우, 3일 경우로 경우의 수가 반복됩니다. 고로 array.forEach 함수로 element 가 순회하면서 돌때마다 element에는 1 , 2, 3 이 들어가게 됩니다. 

 

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

element 는  1이므로 변수 fix 에는 1이 들어가게 됩니다. 

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

fix에는 1이 들어갔을 때 1이아닌 나머지 원소들은 rest 변수에 들어가게됩니다.  

array. forEach ((element, originalArrIndex, array) = {​
 const fix = element; //1
  const rest = array. filter ((_, restArrIndex) => restArrIndex !== originalArrIndex);
  // forEach에서 현재 돌고있는 element의 인덱스값과 다른 요소들만 즉 현재 element가 아닌 것들만 담기
  //[2,3]

4.  첫번째 원소가 1 fix 된 채 나머지 2 개 요소 선정하기  

1일 제외한 나머지 중에 2개를 선정해야함으로 재귀로 자기 자신을 다시 호출합니다.  그리고 그 리턴 값을 permutation0fRest 에 담습니다.  현재  rest 는 [1,2 ] selectNumber 는 3이므로 getPermutation([2,3],2) 가 호출합니다. 

const permutation0fRest = getPermutation (rest, selectNumber - 1) ;

5.  2번째 원소 선정하기 

함수가 자기자신을 호출합니다. 이번에 array값은  인자로 받아온 rest [2,3]이고  selectNumber 는 2가 들어갑니다. selectNumber는 1이 아니므로 if 문을 거치지 않습니다. array 는[2,3]이고 이를 forEach를 돌립니다. 현재 element 는 2입니다.   fix 로 2가 들어가며 Rest 로 나머지 [3]이 들어가게됩니다. 그리고 다시 스스로 getPermutation을 호출한 뒤에 그 리턴값을 permutation0fRest에 담습니다. getPermutation([3],1)을 호출하며 다시 위에 코드로 올라갑니다.

function getPermutation (array, selectNumber) { //array[2,3]이 ,selectNumber에는 2가 들어가게 됩니다. 

 if (selectNumber === 1) return array. map((element) =› [element]);
 const result = [];
 array. forEach ((element, originalArrIndex, array) = { //element =2
 const fix = element;  //2 
  const rest = array. filter ((_, restArrIndex) => restArrIndex !== originalArrIndex); //[3]
const permutation0fRest = getPermutation (rest, selectNumber - 1) ; //getPermutation ([3], 1); 호출

6.  3번째 원소 선정하기 

이번에의 array 는 [3]이며 selectNumber는 1입니다. selectNumber 1이므로 if문조건에 충족합니다. 리턴값으로 array [[3]]을 반환시킵니다.  그러면 getPermutation([3],1)은 호출을 끝나게 되며 5.  2번째 원소 선정하기 로 리턴값[[3]]을 가지고 돌아갑니다. 

function getPermutation (array, selectNumber) { //array[3]이 ,selectNumber에는 1가 들어가게 됩니다. 

 if (selectNumber === 1) return array. map((element) =› [element]);

7.  재귀돌아가기: 5번으로 돌아가기 

현재 element가 2일때, selectNumber가 1일 때 로 돌아갑니다.   7번째 줄 getPermutation (rest, selectNumber - 1)은 리턴값 [[3]]을 가지고 돌아왔음으로  변수 permutation0fRest 에 [[3]]가 담아집니다.

function getPermutation (array, selectNumber) { //[2,3] 2

 if (selectNumber === 1) return array. map((element) =› [element]);
 const result = [];
 array. forEach ((element, originalArrIndex, array) = { //2 
 const fix = element;
  const rest = array. filter ((_, restArrIndex) => restArrIndex !== originalArrIndex);
const permutation0fRest = getPermutation (rest, selectNumber - 1) ; // [[3]] <--- 다시복귀
const combineFix = permutation0fRest .map ((elementArr) = [fix, ... elementArr]);
result.push (... combineFix);
});
return result;
}