자바스크립트 알고리즘 - 자료구조 : 순열

자바스크립트 (JavaScript)

 

자바스크립트 알고리즘 - 자료구조 : 순열에 대한 설명입니다.

 

순열이란?

순서가 의미있는 조합으로 순서가 달라지면 의미가 달라지는 자료구조입니다.

 

설명하자면 아래에 있는 코드처럼 1,2,3,4 라는 값이 들어있는 배열을 3개를 기준으로 순열 방식으로 나열하면

[1, 2, 3]은 [2, 3, 1]과 같은 값을 가지고 있지만 순서가 다르기 때문에 의미가 달라져 둘다 나열되는 것 입니다.

 

아래 코드를 보면 이해하기 편하도록 주석으로 자세하게 달아뒀습니다. :)

 

const getPermutations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return

  arr.forEach((fixed, index, origin) => {
    console.log(fixed, "fixed");
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)] // 해당하는 fixed를 제외한 나머지 배열
    console.log(rest, "rest", selectNumber - 1, "selectNumber - 1");
    
    const permutations = getPermutations(rest, selectNumber - 1); // 나머지에 대해 순열을 구한다.
    console.log(permutations, "permutations");
    
    const attached = permutations.map((permutation) => [fixed, ...permutation]); // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
    console.log(attached, "attached");
    
    results.push(...attached); // 배열 spread syntax 로 모두다 push
    console.log(results, "results");
  });

  return results; // 결과 담긴 results return
};

const example = [1,2,3,4];
const result = getPermutations(example, 3);
console.log(result);
// => [
//   [ 1, 2, 3 ], [ 1, 2, 4 ],
//   [ 1, 3, 2 ], [ 1, 3, 4 ],
//   [ 1, 4, 2 ], [ 1, 4, 3 ],
//   [ 2, 1, 3 ], [ 2, 1, 4 ],
//   [ 2, 3, 1 ], [ 2, 3, 4 ],
//   [ 2, 4, 1 ], [ 2, 4, 3 ],
//   [ 3, 1, 2 ], [ 3, 1, 4 ],
//   [ 3, 2, 1 ], [ 3, 2, 4 ],
//   [ 3, 4, 1 ], [ 3, 4, 2 ],
//   [ 4, 1, 2 ], [ 4, 1, 3 ],
//   [ 4, 2, 1 ], [ 4, 2, 3 ],
//   [ 4, 3, 1 ], [ 4, 3, 2 ]
// ]