[알고리즘/JavaScript] 순열 함수

순열

1. 서로 다른 n개의 물건 중에서 r개를 택하여 한 줄로 배열하는 것을 n개의 물건에서 r개 택하는 순열이라 하고, 이 순열의 수를 기호로 nPr와 같이 나타낸다.

2. 서로 다른 n개에서 r개를 택하는 순열의 수는 

(단, 0 < r ≦ n)

[네이버 지식백과] 순열 (Basic 고교생을 위한 수학공식 활용사전, 2002. 3. 10., 김종호)

 

단순하게 말하자면 한 배열에 4개의 서로 다른 숫자가 들어가있고, 그 중에서 3개의 문자들을 임의로 골라서 중복없이 조합을 시키는 것을 순열이라고 할 수 있다. 

 

원리 

• 하나의 수를 선택한다.
• 하나를 선택했으니 남은 수들 중에서 2개를 선택해야한다. 

이 과정을 반복하면서 만들어진다. 이런 과정을 반복하는 몇가지들이 있는데 이 중에서 순열은 경우의 수이고 일대일대응이다. 뽑아진 3개의 수가 중복이 되더라도 순서가 다르면 다른 수로 받아들인다. 

 

 

순열코드

function permutation(arr, selectNum) {
  let result = [];
  if (selectNum === 1) return arr.map((v) => [v]);


  arr.forEach((v, idx, arr) => {
    //매개변수 배열arr에서 한 숫자를 픽해서 fixer로 넣어준다
    const fixer = v;
    //fixer을 제외한 숫자들만 담은 restArr 배열을 만든다
    const restArr = arr.filter((_, index) => index !== idx);
    //재귀로 남은 수의 배열과 선택 수에서 -1한 수를 넣어서 똑같이 만든다
    const permuationArr = permutation(restArr, selectNum - 1);
    //선택된 fixer와 permuationArr을 합쳐서 result 배열에 넣어준다
    const combineFixer = permuationArr.map((v) => [fixer, ...v]);
    result.push(...combineFixer);
  });
  return result;
}

순열을 구하는 코드라고 나와있는 함수가 있다. for문만을 이용해서 구하는 방법도 있는데 수가 증가할수록 한계점이 있어서 인지 재귀함수를 사용해서 구하는 방법이 더 합리적으로 보인다.  

 

위의 함수를 풀어서 보여준다면

permutation([1,2,3],2)
fixer: 1, restArr: [2,3], permutationArr: permutation([2,3],1)
1-1. permutation([2,3],1)
selectNum ===1 => return [[2],[3]]

이것은 위의 permuatitonArr이 된다.
즉
fixer: 1,
restArr: [2,3],
permutationArr: [[2],[3]],
combineFixer: [[1,2],[1,3]]

result.push([[1,2],[1,3]])

이렇게 1을 먼저 골랐을 때 순열을 구하는 순서이다. 이렇게 2,3을 반복한다.

 

 

 

 

 

 

 

 

 

👉 자료출처 

[JS]순열,조합,중복순열 구하기