주어진 문자열의 모든 순열을 인쇄합니다.

주어진 문자열의 모든 순열을 인쇄하는 것은 역추적 문제의 예입니다. 하위 문제를 해결하기 위해 하위 문자열의 크기를 줄인 다음 다시 역추적하여 해당 섹션에서 다른 순열을 얻습니다.

예를 들어 문자열이 ABC이면 모든 순열은 ABC, ACB, BAC, BCA, CAB, CBA가 됩니다.

이 알고리즘의 복잡도는 O(n!)입니다. 엄청난 복잡성입니다. 문자열 크기가 커지면 작업을 완료하는 데 시간이 오래 걸립니다.

입력 및 출력

Input:
A string “ABC”
Output:
All permutations of ABC is:
ABC
ACB
BAC
BCA
CBA
CAB

알고리즘

stringPermutation(str, left, right)

입력: 문자열 및 문자의 왼쪽 및 오른쪽 인덱스입니다.

출력: 문자열의 모든 순열을 인쇄합니다.

Begin
   if left = right, then
      display str
   else
      for i := left to right, do
         swap str[left] and str[i]
         stringPermutation(str, left+1, right)
         swap str[left] and str[i]             //for backtrack
      done
End

예시

#include<iostream>
using namespace std;

void stringPermutation(string str, int left, int right) {
   if(left == right)
      cout << str << endl;
   else {
      for(int i = left; i<= right; i++) {
         swap(str[left], str[i]);
         stringPermutation(str, left + 1, right);
         swap(str[left], str[i]); //swap back for backtracking
      }
   }
}

int main() {
   string str = "ABC";
   cout << "All permutations of " << str << " is: " <<endl<<endl;
   stringPermutation(str, 0, str.size()-1);
}

출력

All permutations of ABC is:
ABC
ACB
BAC
BCA
CBA
CAB