JavaScript 로 재귀적인 배열 순열 구현하기

소개

이 랩에서는 JavaScript 에서 배열 순열 (array permutations) 의 개념을 탐구합니다. 재귀 (recursion) 를 사용하여 중복된 요소가 포함된 경우에도 배열 요소의 모든 가능한 순열을 생성하는 방법을 배웁니다. 또한 map() 및 reduce()와 같은 Array 메서드를 사용하여 서로 다른 순열을 단일 배열로 결합하는 방법을 이해할 것입니다. 하지만 8~10 개 이상의 요소를 가진 배열에서 이 함수를 실행하면 실행 시간이 크게 증가하고 브라우저가 멈출 수 있다는 점을 명심해야 합니다.

모든 배열 순열 생성 방법

코딩 연습을 시작하려면 터미널/SSH 를 열고 node를 입력하십시오.

다음은 배열 요소의 모든 순열을 생성하는 알고리즘입니다 (중복된 요소가 포함된 경우에도). 이를 구현하려면 다음 단계를 따르십시오.

1. 재귀 (recursion) 를 사용합니다.
2. 주어진 배열의 각 요소에 대해 나머지 요소에 대한 모든 부분 순열을 생성합니다.
3. Array.prototype.map()을 사용하여 요소를 각 부분 순열과 결합한 다음, Array.prototype.reduce()를 사용하여 모든 순열을 하나의 배열로 결합합니다.
4. 기본 사례는 길이가 2 또는 1인 배열에 대한 것입니다.
5. 이 함수의 실행 시간은 각 배열 요소에 따라 기하급수적으로 증가한다는 점에 유의하십시오. 8~10 개 이상의 항목은 모든 서로 다른 조합을 해결하려고 시도하면서 브라우저가 멈출 수 있습니다.

다음은 코드입니다.

const permutations = (arr) => {
  if (arr.length <= 2) return arr.length === 2 ? [arr, [arr[1], arr[0]]] : arr;
  return arr.reduce(
    (acc, item, i) =>
      acc.concat(
        permutations([...arr.slice(0, i), ...arr.slice(i + 1)]).map((val) => [
          item,
          ...val
        ])
      ),
    []
  );
};

배열 인수로 permutations() 함수를 호출하여 코드를 테스트할 수 있습니다.

permutations([1, 33, 5]);
// [ [1, 33, 5], [1, 5, 33], [33, 1, 5], [33, 5, 1], [5, 1, 33], [5, 33, 1] ]

요약

축하합니다! 배열 순열 (Array Permutations) 랩을 완료했습니다. LabEx 에서 더 많은 랩을 연습하여 기술을 향상시킬 수 있습니다.