이번 글에서는 순열(Permutation) 알고리즘에 대해 정리해본다.

순열

  • Permutation
  • 표현: nPr
  • 의미: 서로 다른 n개 중에서 r개를 뽑을 때, 순서를 고려하여 뽑는 경우의 수.
    중복을 포함하지 않는다. (중복을 포함하는 것은 ‘중복 순열’)

순열 알고리즘

순열을 구하는 방법은 조합과 크게 다르지 않다.
배열 [0, 1, 2, 3]에서 3개를 뽑는 경우를 살펴보자. 4P3

  • 0을 선택한 뒤, 나머지 [1, 2, 3]에서 2개의 조합을 구한다.
    1을 선택한 뒤, 나머지 [2, 3]에서 1개의 조합을 구한다.
    …
  • 1을 선택한 뒤, 나머지 [0, 2, 3]에서 2개의 조합을 구한다.
    0을 선택한 뒤, 나머지 [2, 3]에서 1개의 조합을 구한다.
    …
  • 2를 선택한 뒤, 나머지 [0, 1, 3]에서 2개의 조합을 구한다.
    …
  • 3을 선택한 뒤, 나머지 [0, 1, 2]에서 2개의 조합을 구한다.
    …

조합이 처음 요소부터 선택하면서 선택한 요소 뒤의 요소들을 나머지 배열로 구한다면,
순열은 선택한 요소를 제외한 모든 요소를 나머지 배열로 구한다.
이는 순열의 경우, 순서가 의미를 갖기 때문이다.

따라서, 코드에서 조합과의 차이는 다음이 유일하다.

// 조합: 선택한 요소 뒤의 요소들
const rest1 = array.slice(index + 1);

// 순열: 선택한 요소(fixed)를 제외한 나머지
const rest2 = [...array.slice(0, index), ...array.slice(index+1)];

자바스크립트로 구현

function permutation(arr = [], r) {
  const result = [];
  // 1개를 뽑는 경우, 배열의 모든 요소를 반환한다
  if (r === 1) return arr.map(elem => [elem]);

  // 배열의 요소를 차례대로 선택(fixed)한다
  arr.forEach((fixed, index, array) => {
    // 선택한 요소를 제외한 나머지 배열
    const rest = [...array.slice(0, index), ...array.slice(index+1)];

    // 나머지에 대하여 순열을 재귀적으로 계산한다
    const combination = permutation(rest, r - 1);

    // 계산된 결과를 result 배열에 삽입한다
    combination.forEach(elem => result.push([fixed, ...elem]));
  });
  return result;
}

console.log(permutation([0, 1, 2, 3], 3));

순열 결과

순열 역시 데이터를 처리할 때 유용하므로, 함수를 잘 숙지해두면 큰 도움이 된다.

참고자료

  • https://gorakgarak.tistory.com
  • https://pul8219.github.io