반복문만으로 문자열의 모든 순열 구하기 – 백트래킹 없는 순열 생성 알고리즘

이 글에서는 문자열의 모든 순열(permutation)을 구하는 방법을 살펴봅니다. 일반적으로 순열은 재귀 호출과 백트래킹(backtracking) 기법을 사용하면 손쉽게 구할 수 있지만, 여기서는 반복(iteration) 방식만으로 순열을 생성하는 알고리즘을 다룹니다.

예를 들어 문자열 "ABC"의 모든 순열은 {ABC, ACB, BAC, BCA, CAB, CBA}처럼 총 6가지입니다. 핵심 아이디어는 문자열을 먼저 오름차순으로 정렬한 뒤, 사전순(lexicographic order)으로 다음 순열을 계속 찾아내는 것입니다. 그럼 알고리즘을 통해 자세히 살펴보겠습니다.

알고리즘

getAllPerm(str)

begin
   문자열의 문자들을 오름차순으로 정렬한다
   while true, do
      문자열 str을 출력한다
      i := length of str – 1
      while str[i - 1] >= str[i], do  // 뒤에서부터 내림차순이 깨지는 지점을 찾음
         i := i – 1
         if i is 0, then
            return  // 더 이상 다음 순열이 없으면 종료
         end if
      done
      j := length of str – 1
      while j > i AND str[j] <= str[i – 1], do
         j := j – 1
      done
      str[i - 1] 위치의 문자와 str[j] 위치의 문자를 교환한다
      i부터 끝까지의 부분 문자열을 뒤집는다
   done
end

동작 원리 요약

1. 문자열을 오름차순으로 정렬하면 가장 작은 순열(첫 번째 순열)이 됩니다.
2. 뒤쪽에서부터 탐색해 처음으로 str[i-1] < str[i]가 되는 지점(피벗)을 찾습니다. 끝까지 못 찾으면 모든 순열을 출력한 것이므로 종료합니다.
3. 피벗 바로 앞 문자(str[i-1])보다 큰 문자 중 가장 오른쪽에 있는 문자를 찾아 서로 교환합니다.
4. 피벗 위치(i)부터 끝까지를 뒤집어 다음으로 작은 사전순 배열을 만듭니다.
5. 위 과정을 반복하면 모든 순열이 사전순으로 출력됩니다.

C++ 예제 코드

#include <iostream>
#include <algorithm>
using namespace std;
void getAllPerm(string str){
   sort(str.begin(), str.end());  // 첫 순열을 위해 오름차순 정렬
   while (true){
      cout << str << endl;
      int i = str.length() - 1;
      while (str[i-1] >= str[i]){
         if (--i == 0)
         return;  // 마지막 순열(내림차순)에 도달하면 종료
      }
      int j = str.length() - 1;
      while (j > i && str[j] <= str[i - 1])
      j--;
      swap(str[i - 1], str[j]);
      reverse (str.begin() + i, str.end());
   }
}
int main(){
   string str = "WXYZ";
   getAllPerm(str);
}

실행 결과

WXYZ
WXZY
WYXZ
WYZX
WZXY
WZYX
XWYZ
XWZY
XYWZ
XYZW
XZWY
XZYW
YWXZ
YWZX
YXWZ
YXZW
YZWX
YZXW
ZWXY
ZWYX
ZXWY
ZXYW
ZYWX
ZYXW

실행 결과를 보면 문자열 "WXYZ"의 24가지 순열이 사전순으로 정확히 출력되는 것을 확인할 수 있습니다. 이 방식은 재귀 함수 호출로 인한 스택 오버플로우 걱정 없이, 반복문만으로 안정적으로 모든 순열을 생성할 수 있다는 장점이 있습니다.