다음 순열(next permutation) 알고리즘

“다음 순열(Next Permutation)” 알고리즘은 주어진 순열에서 사전 순으로 다음에 오는 순열을 구하는 알고리즘이며, STL(Standard Template Library)에서도 제공됩니다. 이 알고리즘은 순열에 대한 문제를 풀거나, 모든 순열을 나열해야 하는 경우에 유용하게 사용됩니다.

다음 순열 알고리즘의 과정은 다음과 같습니다:

뒤쪽부터 탐색하며, 숫자가 감소하는 경계를 찾습니다. (arr[i – 1] < arr[i])
다시 뒤쪽부터 탐색하며, 경계보다 큰 첫 번째 숫자를 찾습니다. (arr[j] > arr[i – 1])
두 숫자의 위치를 바꿉니다. (swap(arr[i – 1], arr[j]))
경계에서부터 끝까지의 숫자를 뒤집습니다. (reverse(arr[i], arr[end]))

이렇게 하면 사전 순으로 바로 다음에 오는 순열을 구할 수 있습니다.

예를 들어, [1, 2, 3]의 다음 순열은 [1, 3, 2]가 됩니다.

이를 JavaScript로 구현하면 다음과 같습니다:

function nextPermutation(arr) {
  let i = arr.length - 1;
  while (i > 0 && arr[i - 1] >= arr[i]) {
    i--;
  }
  if (i <= 0) {
    return false;  // 마지막 순열
  }
  let j = arr.length - 1;
  while (arr[j] <= arr[i - 1]) {
    j--;
  }
  [arr[i - 1], arr[j]] = [arr[j], arr[i - 1]];  // swap
  j = arr.length - 1;
  while (i < j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];  // reverse
    i++;
    j--;
  }
  return true;
}

이 함수는 주어진 배열이 마지막 순열이면 false를 반환하고, 아니면 true를 반환합니다. 따라서 이 함수를 사용하여 모든 순열을 나열하려면, 첫 순열에서 시작하여 이 함수를 반복 호출하면 됩니다.

답글 남기기 응답 취소