순열 알고리즘

이 글에서는 순열을 재귀를 통해서 구현하는 방법에 대해서 알아보자.

순열은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 순열이라고 한다. 순서가 존재하는 열 이라는 것 이다.

즉, 순열에서 { 1, 2, 3 } 과 { 1, 3, 2 } , { 2, 1, 3 } .. 등은 순서가 다르기 때문에 모두 다른 결과를 뜻한다.

순열과 조합의 차이점은 순서가 있냐 없냐의 차이이다.

조합에는 순서가 없기 때문에, 과거에 시작점으로 삼았던 기준점은 무시하였지만 순열은 과거에 시작점으로 삼았던 기준점을 무시하면 안된다.

조합 → { 1, 2, 3 } = { 2, 1, 3 } 이므로, 시작점이 2가 되는 순간 더 작은 요소인 1은 무시한다.

순열 → { 1, 2, 3 } != { 2, 1, 3 } 이므로, 시작점이 2가 되더라도 더 작은 요소인 1을 무시하면 안된다.

구현 코드

const MAX = 5;
const result = [];

const permutation = () => {
  const arr = [1, 2, 3, 4, 5]; // 순열에 사용되는 배열
  const selected = new Array(MAX).fill(false); // 이 배열을 통햏 중복을 허용하지 않도록 해야한다.

  dfs(0, arr, selected);
};

const dfs = (cnt, arr, selected) => {
  // 조합과 달리 idx 변수가 없어진 이유는 조합과 달리 순열은 시작점을 무시하면 안되기 때문이다.
  // cnt는 현재 뽑은 원소의 갯수를 결정해주는 변수이다. 현재 뽑은 원소의 갯수가 우리가 최종적으로 뽑고자 하는 원소의 갯수와 일치한다면, 그 다음 프로세스를 진행하면 된다.

  if (cnt === 3) {
    console.log(result.join(" "));

    return;
  }

  for (let i = 0; i < MAX; i++) {
    if (selected[i] === true) continue;

    selected[i] = true;
    result.push(arr[i]);
    dfs(cnt + 1, arr, selected);
    result.pop();
    selected[i] = false;
  }
};

permutation();